1주차 모범 답안

[dhdbstjr98]

개요

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

모범 답안

1. 숫자 카드 게임

문제 보기

정답 : 13명

손현수

counting을 이용한 풀이

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

int cardCnt[100001], minPoint=100001, maxPoint, n, k, cardNum, sum;

int main(){
	scanf("%d%d",&n,&k);
	for(int cnt=0;cnt<n;++cnt){
		scanf("%d", &cardNum);
		++cardCnt[cardNum];
		minPoint = min(minPoint, cardNum);
		maxPoint = max(maxPoint, cardNum);
		sum+=cardNum;
	}
	
	for(int cnt=1;cnt<=k;++cnt){
		if(cnt&1){
			while(!cardCnt[minPoint]) ++minPoint;
			sum-=minPoint;
			--cardCnt[minPoint];
		}
		else{
			while(!cardCnt[maxPoint]) --maxPoint;
			sum-=maxPoint;
			--cardCnt[maxPoint];
		}
	}
	printf("%d",sum);
	return 0;
}

박진수

정렬을 이용한 풀이

# 숫자 카드 게임 ㅎㅅㅎ
length, numOfTurns = map(int, input().split())
cards = sorted([int(card) for card in input().split()])

# 굳이 이렇게 반복문을 돌릴 필요 없이
# for i in range(1, numOfTurns + 1):
#     if i % 2 == 1:
#         cards = cards[1:]
#     else:
#         cards = cards[:-1]

# 생각해보면 그냥 짤릴 앞 뒤는 정해져있으니
cards = cards[(numOfTurns+1)//2:length - numOfTurns//2]

print(sum(cards))

# print(cards)

2. 하노이의 탑

문제 보기

정답 : 14명

손현수

일반항을 계산한 풀이

#include <cstdio>

unsigned long long result=1;
int n;

//1 <= n <= 62 계산 가능
//식은.. 원반이 처음에 위치한 자리에 따리 거쳐가는 막대의 경로가 같기 때문에
//그것을 이용한 O(1)의 일반향입니다.. f(n) = n + 2^(n+1) - 2

int main() {
	scanf("%d",&n);
	result<<=n+1;
	printf("%llu",n+result-2);
	return 0;
}

심규진

점화식을 계산한 풀이

def solve():
    N = int(input())
    # 상태를 3개로 나누자. 
    # now, sub, main / 시작점, 둘다 아닌 곳, 도착점 
    moves = [[0,0,0] for i in range(N+1)]
    moves[0][2] = 1#[0,0,1]

    for i in range(1,N):
        [bef_now, bef_sub, bef_main] = moves[i - 1]
        # 점화식 성립
        moves[i] = [bef_now + bef_sub, bef_main + bef_now, bef_sub + bef_main + 1]
    print(sum([(i+1) * moves[N-1][i] for i in range(3)]))
solve()

전현준

재귀를 이용한 풀이

def hanoi(f, t, n):
    return t if n==1 else hanoi(f, 6-f-t, n-1) + t + hanoi(6-f-t, t, n-1)

print(hanoi(1, 3, int(input())))

3. 연산자 끼워넣기

문제 보기

정답 : 12명

윤창목

permutation을 이용한 풀이

import itertools

def cal(h, o):
    res = nums[0]
    for i in range(0,len(o)):
        if o[i] == '0':
            res += nums[i+1]
        elif o[i] == '1':
            res -= nums[i+1]
        elif o[i] == '2':
            res *= nums[i+1]
        elif o[i] == '3':
            if res < 0:
                res = -((-res)//nums[i+1])
            else:
                res = res//nums[i+1]
    h.append(res)

n = int(input())
nums = list(map(int, input().split()))
ops = list(map(int, input().split()))
perm = []
for i in range(0, 4):
    for j in range(0, ops[i]):
        perm.append(str(i))
perm = list(map(''.join, itertools.permutations(perm, len(perm))))
history = []
perm_set = set(perm)
perm = list(perm_set)
for i in range(len(perm)):
    cal(history, perm[i])

print(max(history))
print(min(history))

전현준

브루트포싱을 이용한 풀이

maxi, mini = -10**9, 10**9

def fn(num, i, a, b, c, d):
    if a+b+c+d:
        if a:
            fn(num+arr[i], i+1, a-1, b, c, d)
        if b:
            fn(num-arr[i], i+1, a, b-1, c, d)
        if c:
            fn(num*arr[i], i+1, a, b, c-1, d)
        if d:
            fn(int(num/arr[i]), i+1, a, b, c, d-1)
    else:
        global maxi, mini
        maxi, mini = max(maxi, num), min(mini, num)

n = int(input())
arr = list(map(int, input().split()))
fn(arr[0], 1, *map(int, input().split()))
print(maxi)
print(mini)

4. 징검다리 건너기

문제 보기

정답 : 8명

황지원

binary search를 이용한 풀이

n, k = map(int, input().split())
stones = list(map(int, input().split()))


# if k == 1, success member is min(stones)
# if k == n, success member is max(stones)
left = min(stones)
right = max(stones)
count = 0
member = right

# binary search
while left <= right:
    mid = (left + right) // 2
    count = 0
    valid = True

    # check mid member
    for stone in stones:
        # if stone < member, stone will be zero before passing
        if stone < mid:
            count += 1
        else:
            count = 0

        # fail : if k zeros in a row, you should jump k+1
        # should check less member
        if count >= k:
            valid = False
            right = mid-1
            break

    # success
    # should check more member
    if valid == True:
        member = mid
        left = mid+1

print(member)

손현수

세그먼트 트리를 이용한 풀이

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

#define INT_MAX (1<<31)-1

//n,k,stones는 입력받는 값을 저장할 변수, rangeMaxTree, pnt(=point)는 세그먼트 트리를 구현하기 위한 변수 / <<X는 *(2의 X제곱)과 같음.
int n,k,stones[200020], rangeMaxTree[1<<21], pnt=1;

//세그먼트 트리를 업데이트 하는 함수
void update(int node, int value){
	//node에 point를 더해 세그먼트 트리의 리프노드를 향하게 만들고
	//리프노드는 구간이 하나니까 max값을 계산하는 대신 값을 그대로 저장함
	node += pnt; 
	rangeMaxTree[node] = value;
	
	//그 뒤로 루트노드까지 노드의 부모노드를 방문해서 max값을 재계산함.
	while(node/=2)
		rangeMaxTree[node] = max(rangeMaxTree[node*2], rangeMaxTree[node*2+1]); 
}

int getRangeMax(int srt, int end){
	//구간의 시작과 끝점에 point를 더해 세그먼트 트리의 리프노드를 향하게 만듦 + 초기값 세팅
	srt += pnt, end += pnt;
	int maxNum = 0;
	
	//리프노드들부터 올라가면서 구간의 max값을 구함.
	while(srt<=end){
		
		//start가 홀수일 때 더 이상 합칠 구간이 없으므로 max값에 반영 후 start 한 칸 오른쪽으로 이동
		if(srt&1) maxNum = max(maxNum,rangeMaxTree[srt++]);
		
		//end가 짝수일 때 더 이상 합칠 구간이 없으므로 max값에 반영 후 end 한 칸 왼쪽으로 이동
		if(!end&1) maxNum = max(maxNum, rangeMaxTree[end--]);
		
		//start와 end 모두 부모노드로 올라감. >>=X는 /=(2의 X제곱)과 같음.
		srt>>=1, end>>=1;
	}
	return maxNum;
}


// 알고리즘
// n번째 징검다리에서 건널 수 있는 최대 인원수 = (n-k~n-1번째 징검다리에서 건널 수 있는 최대 인원수) 와 (n번째 징검다리에서 건널 수 있는 인원수) 중 최솟값
// 이라 생각하고 구현했습니당
// 세그먼트 트리는 이 때 [n-k,n-1] 구간의 최댓값을 빨리 구하려고 만드는 것

int main(){
	scanf("%d%d",&n,&k);
	for(int cnt=1; cnt<=n; ++cnt)
		scanf("%d", &stones[cnt]);
	
	//point가 가리킬 위치를 계산하는 것, 세그먼트 트리를 완전 이진 트리로 만들어서 계산에 용이하도록 만듦 
	while(pnt<=n) pnt<<=1;
	
	
	update(0, INT_MAX);//INT_MAX는 #define 참고, 처음(0번째 징검다리 = 지상)에는 무제한으로 건너올 수 있으니까 반영함
	for(int dpCnt=1; dpCnt<=n; ++dpCnt){
		//maxNum : 구간 중 건널 수 있는 최대 인원수, possibleMember = dpCnt번째 징검다리에서 건널 수 있는 최대 인원수
		int maxNum = getRangeMax(max(0,dpCnt-k), dpCnt-1),
			possibleMember = min(stones[dpCnt], maxNum);
		
		//다음 계산을 위해 세그먼트 트리에 반영
		update(dpCnt, possibleMember);
		
		//한 줄로 바꾸면 아래가 됨
		//update(dpCnt, min(getRangeMax(max(0,dpCnt-k),dpCnt-1), stones[dpCnt]));
	}
	
	//도착지점에서의 구간 최댓값을 구하면 원하는 결과를 얻을 수 있음
	printf("%d",getRangeMax(n-k+1,n));
	return 0; 
}

5. 도둑질

문제 보기

정답 : 8명

박민재

dp를 이용한 풀이

n = int(input())
money = list(map(int, input().split()))

dp = [0 for i in range(n)]  # 처음꺼 포함
dp[0], dp[1] = money[0], money[0]

for i in range(2, n - 1):
    dp[i] = max(dp[i - 1], dp[i - 2] + money[i])

dp2 = [0 for i in range(n)]  # 끝꺼 포함
dp2[0], dp2[1] = 0, money[1]

for i in range(2, n):
    dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i])

print(max(dp[n - 2], dp2[n - 1]))

정산

• 손현수 x 3
• 전현준 x 2
• 박진수
• 심규진
• 윤창목
• 황지원
• 박민재

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

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

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

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

[bluejoyq]

역시 알고리즘 왕 손선생님...

[all-eviate]

import itertools #permutation을 사용하기 위함입니다.

def cal(h, o): #연산자의 순열대로 숫자를 계산하는 함수입니다.
    res = nums[0]
    for i in range(0,len(o)):
        if o[i] == '0': #덧셈
            res += nums[i+1]
        elif o[i] == '1': #뺄셈
            res -= nums[i+1]
        elif o[i] == '2': #곱셈
            res *= nums[i+1]
        elif o[i] == '3': #나눗셈 (규칙에 맞게 경우를 나눠서 계산합니다.)
            if res < 0:
                res = -((-res)//nums[i+1])
            else:
                res = res//nums[i+1]
    h.append(res) #계산 결과를 기억합니다.

n = int(input())
nums = list(map(int, input().split()))
ops = list(map(int, input().split()))
perm = [] #연산자의 순열들을 기억하는 리스트입니다.

#아래 for문은 갯수로 주어진 연산자들을 각 갯수대로 나열합니다.
for i in range(0, 4):
    for j in range(0, ops[i]):
        perm.append(str(i))

#위 for문에서 완성한 연산자가 나열된 리스트의 원소들을 이용해 가능한 모든 순열을 perm에 저장합니다.
perm = list(map(''.join, itertools.permutations(perm, len(perm))))

history = [] #각 순열에 해당하는 연산 결과를 저장하는 리스트입니다.

#위에서 만든 순열 리스트의 중복되는 순열을 제거하기 위해 한번 집합으로 바꿨다 돌려줍니다.
perm_set = set(perm)
perm = list(perm_set)

#각 순열의 연산자 순서대로 계산하도록 함수를 호출합니다.
for i in range(len(perm)):
    cal(history, perm[i])

#끝!
print(max(history))
print(min(history))

[umi0410]

허걱 ㅋㅋㅋ 연산자 문제 설마 브루트포스일까 했는데 ㄱ-...

[Untaini]

하노이의 탑 일반항 유도과정이 궁금하신 분들은 제 브랜치 1-week1/2 에 있는 General Clauses를 참고하시면 되겠습니다