Dp

백준 2670번 바로가기 첫 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) s = [] for i in range(n): temp = l[i] s.append(temp) for j in range(i+1,n): temp *= l[j] s.append(temp) print(round(max(s),3)) 메모리 초과 두 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) max = max(l) for i in range(n): temp = l[i] for j in range(i+1,n): temp *= l[j] if temp > max: max = temp print(round(max, 3)) 시간 초과 세 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) m = max(l) for i in range(n): temp = l[i] for j in range(i+1,n): temp *= l[j] if temp > m: m = temp print('%.3f' % m) 고수의 풀이 n=int(input()) a=[float(input())for _ in[0]*n] for i in range(1,n):a[i]=max(a[i-1]*a[i],a[i]) print(f'{max(a):.3f}') 출처 CODE REVIEW 메모리 초과 문제를 해결하기 위해 list에서 max를 뽑아내지 않고 m(현재 최댓값)보다 크면 update, 크지 않다면 그대로 pass로 바꾸어주었다. 문제 출력 형식이 소수 셋째 자리까지 맞추어줘야하므로 round()함수 대신 '%.3f % m처럼 소숫점 출력 형식으로 바꾸어주었다. 고수의 풀이 방식이 메모리도 덜 차지하고 시간도 빠른데, 각 자리별로 구할 수 있는 max값을 a[i]에 할당하고, 그것의 max를 구한다는 아이디어였다. python에서 max, min같은 이름은 변수에 붙이지 않는걸 권장한다! 웬만하면 다른 이름을 쓰자

백준 9656번 바로가기 나의 풀이 game = [""] * 1001 game[1] = "CY" game[2] = "SK" game[3] = "CY" for i in range(4, (n:=int(input()))+1): if game[i-1] == "CY" or game[i-3] == "CY": game[i] = "SK" else: game[i] = "CY" print(game[n]) 고수의 풀이 print('SCKY'[int(input())%2::2]) 출처 CODE REVIEW 백준 9655 의 연장선의 문제. 규칙이 매우 쉬워서 금방 풀어낼 수 있다. 갯수가 홀수/짝수냐에 따라 이기는 사람이 달라서, 어이없게(?) 고수의 풀이 처럼 풀어낼 수도 있긴 하다.

백준 13301번 바로가기 나의 풀이 n = int(input()) f = [1]*(n+1) for i in range(2, n+1): f[i] = f[i-1] + f[i-2] if n < 2: print(4) else: print(2*(2*f[n-1]+f[n-2])) 고수의 풀이 a=b=1;exec('a,b=b,a+b;'*int(input()));print(b*2) 출처 CODE REVIEW 피보나치 수열을 구하고, 길이에 대한 일반항만 구하면 쉽게 해결 가능한 문제였다. 고수의 풀이를 보면 길이를 간단하게 피보나치 n항의 2배로 구했는데, 논리를 따져보면… (둘레) = $2(2a_{n-1}+a_{n-2})$ = $2(a_{n}+a_{n-1})$ = $2a_{n+1}$ 따라서 피보나치 수열의 n+1항의 2배가 둘레와 같다.

백준 13699번 바로가기 나의 풀이 t = [1,1,2,5] + [0] * 36 if (n:=int(input())) > 3: for i in range(4,n+1): for j in range(i): t[i] += t[j]*t[i-j-1] print(t[n]) 고수의 풀이 import math n=int(input()) print(math.comb(2*n,n)//(n+1)) 출처 CODE REVIEW 이중 for문을 범위에 알맞게 구현하면 원하는 답을 얻을 수 있었다. 예전에 창의력 수학 문제를 푸는 기분이 든다. 고수의 풀이에서는 Combination 조합을 이용해서 문제를 풀어내었다. ${2n \choose n}$ 을 (n+1)로 나눈 몫이 답과 동일한 모양… 근데 문제 제목부터 점화식이라 규칙을 찾아 푸는 방식이 출제의 의도와 적합할 듯 하다…!

백준 14916번 바로가기 나의 풀이 c = int(input()) arr = [0,2,1,3,2,1,3,2,4,3] if c == 1 or c == 3: print(-1) else: print((c//10)*2 + arr[c%10]) 고수의 풀이 n=int(input()) print((n//5+[0,2,1,3,2][n%5],-1)[n in(1,3)]) 출처 CODE REVIEW 두 자리 숫자부터는 10=5원*2로 생각해서 10마다 2씩 늘려주면된다. 따라서 거스름돈을 10으로 나눈 몫(q)과 나머지(r)에 집중해서 풀면 된다. 고수의 풀이의 경우 5로 나눈 몫과 나머지를 가지고 문제를 풀어주었다. 나머지 논리는 동일!