7주차 모범 답안

[dhdbstjr98]

개요

• 평균 점수 : 6.2점 (미참여자 제외)
• 만점자 : 2명

모범 답안

1. 젠가

문제 보기

정답 : 10명

황지원

stack을 이용한 풀이

n, m = map(int, input().split())
blocks = list(map(int, input().split()))


sum = 0
count = 0
center = 0
base = 0

# check from last block
while blocks and base-m < center < base+m:
    sum += blocks.pop()
    count += 1
    center = sum / count
    try:
        base = blocks[-1]
    except:
        break


if count == n:
    print(1)
else:
    print(0)

2. 키로거

문제 보기

정답 : 7명

황지원

doubly linked list를 이용한 풀이

str = list(input())


# double linked list
class Node:
    def __init__(self, char=''):
        self.char = char
        self.next = None
        self.prev = None

    def add(self, char):
        node = Node(char)
        node.prev = self
        node.next = self.next
        if self.next:
            self.next.prev = node
        self.next = node

    def delete(self):
        self.prev.next = self.next
        if self.next:
            self.next.prev = self.prev
        del self

head = Node('head')
cursor = head

for c in str:
    if c == '<':
        if cursor.char != 'head':
            cursor = cursor.prev
    elif c == '>':
        if cursor.next:
            cursor = cursor.next
    elif c == '-':
        if cursor.char != 'head':
            temp = cursor
            cursor = cursor.prev
            temp.delete()
    else:
        cursor.add(c)
        cursor = cursor.next


cursor = head.next
while cursor:
    print(cursor.char, end='')
    cursor = cursor.next

전현준

stack을 이용한 풀이

from collections import deque

left, right = deque(), deque() #stack
for key in input():
    try:
        if key == '<':
            right.appendleft(left.pop())
        elif key == '>':
            left.append(right.popleft())
        elif key == '-':
            left.pop()
        else:
            left.append(key)
    except IndexError:
        continue
print(''.join(left+right))

3. 쿠키 구입

문제 보기

정답 : 6명

심규진

투 포인터를 이용한 풀이

def solution():
    # 2000 * 500은 백만.
    N = int(input())
    cookies = list(map(int, input().split()))
    
    # i는 경계선으로 i를 꼭 포함해야한다.
    
    result = 0
    for i in range(N - 1):
        boy = cookies[i]
        girl = cookies[i+1]
        boy_left = i
        girl_right = i + 1
        while not (boy_left == 0 and girl_right == N - 1):
            if boy == girl:
                result = max(boy, result )
                if boy_left == 0:
                    girl_right += 1
                    girl += cookies[girl_right]
                else:
                    boy_left -= 1
                    boy += cookies[boy_left]
            elif boy > girl:
                if girl_right == N- 1:
                    break
                girl_right += 1
                girl += cookies[girl_right]
            elif boy < girl:
                if boy_left == 0:
                    break
                boy_left -= 1
                boy += cookies[boy_left]
        if boy == girl:
            result = max(boy, result )
    return result
print(solution())

손현수

binary search를 이용한 풀이

#include <cstdio>

#define max(a,b) (a>b?a:b)

//sumCookies : 1~n까지 쿠키의 누적합
int n, cookie, sumCookies[2001], res;

//[a,b], [b+1,c]중 b를 담당하는 이진 탐색
//a,c가 정해져 있으면 각 구간의 합이 동일하게 만드는 b는 여러개라도 동일한 구간의 합의 값은 단 1개이다.
//또한 f(x) = [a,x] - [x+1,c]로 두면 f(x)는 증가함수 이므로 이를 이용해 이진탐색이 가능하다.
int binary_search(int eLeft, int eRight){
	
	//rSum = [1,eRight] - [1,eLeft], 즉, [1,c] - [1,a-1] = [a,c] // mid가 b의 역할을 함
	int left = eLeft+1, right = eRight, mid, lSum, rSum = sumCookies[eRight]-sumCookies[eLeft];
	
	while(left<=right){
		//lSum = [1,b] - [1,a-1] = [a,b]
		mid = (left+right)/2, lSum = sumCookies[mid]-sumCookies[eLeft];
		
		//[a,b] == [b+1,c] ==> [a,b] == [a,c]-[a,b] ==> 2*[a,b] == [a,c]
		if(2*lSum == rSum) return lSum;
		else if(2*lSum > rSum) right = mid-1;
		else left = mid+1;
	}
	return -1;
}

int main() {
	scanf("%d",&n);
	//[a,b], [b+1,c]중 c를 담당하는 for문
	for(int cnt=1; cnt<=n; ++cnt){
		scanf("%d",&cookie);
		//값을 입력 받으면서 바로 구간합을 갱신함
		sumCookies[cnt] = sumCookies[cnt-1]+cookie;
		
		//[a,b], [b+1,c]중 a를 담당하는 for문, srtBasket == a-1임
		for(int srtBasket = 0; srtBasket<cnt; ++srtBasket){
			//binary search를 이용해서 구간의 합을 찾고 답을 갱신함
			res = max(res, binary_search(srtBasket, cnt));
		}
	}
	
	printf("%d", res);
	
	return 0;
}

4. 단어 퍼즐

문제 보기

정답 : 4명

송용우

dp를 이용한 풀이

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

vector<string> words;
const int MAX = 99999999;
int dp[20005];
int main(){
	int n;
	string str;
	cin >> n;

	cin >> str;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		words.push_back(s);
	}
	
	for(int i = 1; i <= str.length(); i++){
		dp[i] = MAX;
	}
	
	for(int i = 1; i <= str.length(); i++){
		for(int j = 0; j < words.size(); j++){
			string s = words[j];

			if(i - s.length() < 0){
				continue;
			}
			bool flag = true;
			for(int k = 0; k < s.length(); k++){
				if(s[k] != str[i - s.length() + k]){
					flag = false;
					break;
				}
			}
			if(flag){
				dp[i] = min(dp[i], dp[i - s.length()] + 1);
			}
		}
	}
	int ans = dp[str.length()];
	if(ans == MAX){
		cout << -1;
	}else{
		cout << ans;
	}
	return 0;
}

손현수

trie + dp를 이용한 풀이

//Trie + DP로 풀기
#include <cstdio>
#include <cstring>
#define min(a,b) (a<b?a:b)

class Trie{
public:
    Trie* abt[26];
    bool isEnd; //끝난지점을 확인하기 위해 변수 추가
	
    Trie(){
        memset(abt, 0, sizeof(abt));
		isEnd=false;
    }
    
    ~Trie(){
        for(int cnt=0; cnt<26; ++cnt)
            if(abt[cnt]) delete abt[cnt];
    }
    
    Trie* insert(int ch){
        if(!abt[ch-='a'])
			abt[ch] = new Trie();
        return abt[ch];
    }
};

//wordDp[n] : n-1번째 문자열을 완성하는데까지 사용한 단어의 최소 개수
int n, wordDp[20010], cnt, len, cur;
char str[20010], word[6];
Trie root;
Trie* trie;

int main(){
	scanf("%d",&n); getchar();
	scanf("%s", str);
	for(cnt=0; cnt<n; ++cnt){
		scanf("%s",word);
		trie = &root;
		
		//단어를 트라이 자료구조에 넣음
		for(cur=0; word[cur]; ++cur)
			trie = trie->insert(word[cur]);
		
		//단어의 마지막 알파벳 위치에 단어가 끝났다는 것을 저장함
		trie->isEnd = true;
	}
	
	//DP 초기값 설정
	for(cnt=1; cnt<=20000; ++cnt)
		wordDp[cnt] = 1<<30;
	
	for(len=0; str[len]; ++len){
		trie = &root, cur=len;
		
		//문자열이 끝나지 않았고 트라이에 str[cur]에 해당하는 알파벳이 없을 때까지 반복
		while(str[cur] && (trie = trie->abt[str[cur++]-'a'])){
			
			//단어가 끝났다면 DP값을 갱신함
			if(trie->isEnd) wordDp[cur] = min(wordDp[cur], wordDp[len]+1);
		}
	}
	
	//주어진 단어들로 문자열을 만들 수 없다면 -1, 아니면 dp값을 출력함
	printf("%d", wordDp[len]==(1<<30)?-1:wordDp[len]);
	return 0;
}

5. 디닷컴 주식회사

문제 보기

정답 : 2명

손현수

dp를 이용한 풀이

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

//dp[n] : n을 루트로 하는 서브 트리에서 ([0] : n을 포함하지 않고, [1] : n을 포함하고) 서브 트리의 모든 팀을 참여시킬 때의 매출액의 최솟값
int n, sales[300001], leader, member, dp[300001][2];
vector<vector<int>> tree(300001,vector<int>());
stack<pair<int, int>> funcStack;

int main(){
	scanf("%d",&n);
	for(int cnt=0;cnt<n;++cnt)
		scanf("%d",&sales[cnt]);
	
	for(int cnt=1;cnt<n;++cnt){
		scanf("%d%d",&leader,&member);
		tree[leader].push_back(member);
	}
	
	//재귀함수 대신 funcStack 사용
	funcStack.push(make_pair(0,0));
	while(!funcStack.empty()){
		int leader = funcStack.top().first, mode = funcStack.top().second;
		funcStack.pop();
		
		//mode가 0일 때는 재귀적으로 각 서브 트리로 진입함
		if(!mode){
			funcStack.push(make_pair(leader,1));
			for(int cnt=0;cnt<tree[leader].size();++cnt)
				funcStack.push(make_pair(tree[leader][cnt],0));
		}
		
		//mode가 1일 때 팀원노드들은 모두 계산이 완료되어 있으므로 팀장노드를 계산함
		else{
			//팀장 노드가 들어갈 때(dp[leader][1])는 항상 팀장의 팀이 들어가니까
			//팀원들이 들어가든 말든 상관없이 (팀원하위팀 매출액 최솟값의 합 + 팀장 매출액) 이 최솟값이 됨

			//팀장 노드가 들어가지 않을 때(dp[leader][0])는 팀원 1명 이상이 무조건 들어가 있어야 하니
			//sumMembers를 이용해서 예외상황을 처리함
			int sumMembers = 0;
			for(int cnt=0; cnt<tree[leader].size(); ++cnt){
				member = tree[leader][cnt];
				dp[leader][0] += min(dp[member][0], dp[member][1]), sumMembers += dp[member][0];
			}
			dp[leader][1] = dp[leader][0]+sales[leader];
			
			//dp[leader][0]은 현재 (팀원하위팀 매출액 최솟값의 합)이기 때문에 이게 sumMembers이랑 같다는 건
			//팀원이 한명도 들어가 있지 않다고 추측할 수 있음
			if(tree[leader].size() && dp[leader][0] == sumMembers){
				
				//따라서 팀원을 한 명씩 넣어보면서 최솟값을 갱신함 
				dp[leader][0] = (1<<31)-1;
				for(int cnt=0; cnt<tree[leader].size(); ++cnt){
					member = tree[leader][cnt];
					dp[leader][0] = min(dp[leader][0], sumMembers-dp[member][0]+dp[member][1]);
				}
			}
		}
	}
	
	//CEO가 들어간 최솟값과 제외한 최솟값 중 더 작은 값을 출력함
	printf("%d", min(dp[0][0], dp[0][1]));
	return 0;
}

정산

• 손현수x3
• 황지원x2
• 전현준
• 심규진
• 송용우

모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.

코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.

해설은 본 이슈에 계속 달아주세요!

모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.