[99클럽 코테 스터디 28일차 TIL] 백준은 오랜만!!

0. 백준 vs 프로그래머스

백준은 문제 수가 많고 알고리즘이 유형별/단계별로 분리되어 있다는 장점이 있지만 ide가 없고 입력을 직접 처리해주어야 해서 불편하다. 반면, 프로그래머스는 문제의 수가 적지만 ide가 있어서 편리하고 대부분의 온라인 코딩테스트 환경과 동일해서 코딩테스트 대비하기에 좋다.

 

난 보통 크게 어려운 문제가 아니고서는 디버깅보단 print로 직접 확인하는 편이기도 하고, 프로그래머스가 UX/UI도 더 깔끔해서 백준보다는 프로그래머스를 선호한다. 그렇지만 어차피 더 많은 문제를 풀기 위해 슬슬 백준으로 옮겨가야 했는데 마침 앞으로 미들러 문제는 백준으로 내주신다니! 백준이랑도 빨리 정 붙여야지 ㅎㅎ

초코파이 정 ㅋㅎㅋㅎㅋ

1. 99클럽 Python 미들러 문제 풀이

[백준 / 17504 / 실버 5. 제리와 톰2]

https://www.acmicpc.net/problem/17504

17504번: 제리와 톰 2

주어진 정수를 이용하여 위의 사진과 같은 식만큼 제리가 치즈를 훔쳐갔을 때 톰에게 남은 치즈의 무게를 구하는 문제였다.

 

문제를 보자마자 재밌겠다 싶었다! 보통 저런 수학 문제는 규칙이 존재하니까 규칙부터 찾기!

위의 사진을 보면 전 단계의 분수의 분모의 값이 다음 단계에선 분자가 되는 것을 알 수 있다.
이렇듯 n = 4, 각 분수의 분모의 값은 x(i), 주어진 정수는 a(i) (2, 7, 1, 8)라고 할 때 점화식은 다음과 같다.
x(0) = 1, x(1) = a(n - 1)

x(i) = x(i - 1) * a(n - i) + x(i - 2) (2 <= i <= n)

 

위 점화식을 계산해 보자

x(0) = 1

x(1) = 8

x(2) = x(1) * a(2) + x(0) = 8 * 1 + 1 = 9

x(3) = x(2) * a(1) + x(1) = 9 * 7 + 8 = 71

x(4) = x(3) * a(0) + x(2) = 71 * 2 + 9 = 151

 

제리가 뺏어간 치즈는 x(n - 1) / x(n), 즉 71/151이 된다. 그렇다면 톰에게 남은 치즈는 1 - 71/151을 계산해 주면 된다.

 

코드에서는 위의 점화식 속의 x를 result 리스트로, a를 num 리스트로 바꾸어 작성했다.

n = int(input())
num = list(map(int, input().split()))
result = [1] * (n + 1)
result[1] = num[n - 1]

for i in range(2, n + 1):
    result[i] = result[i - 1] * num[n - i] + result[i - 2]

print(result[n] - result[n - 1], result[n])

 

우왕 Python에서는 10위다 우하하

 

2. 회고

사실 다 까먹었지만 그래도 수학은 너무 재밌다. 다시 고등학생 때로 돌아가서 수학 공부나 하고 싶은 마음.. 나 언제 척척 학사가 되어버린 거니.. 아무튼 면접 스터디 준비하다가 머리 좀 리프레시할 겸 코테 문제 풀어봤다. 다시 준비하러 가야지..