점화식은 생각났지만 구현하는 부분이 감이 안오다가 바로 깨우치고 만들었다. 1234567891011121314a = int(input())l = list(map(int, input().split(' ')))\ # dp용 배열dp = [0, l[0]] for i in range(2, a + 1): # 이전까지의 계산결과를 dp에 저장하고 # l[i] 와 (여기선 한칸씩 앞으로 되있으니까 i - 1로 코딩) # dp[1] + dp[i - 1], dp[2] + dp[i - 2].... 을 비교해서 가장 큰걸 dp[i]로 넣는다. dp.append(max([dp[z+1] + dp[i - z - 1] for z in range(i//2)] + [l[i - 1]])) print(dp[-1]) Colored by C..

이런 류의 문제를 어떻게 접근할지 몰랐는데 찾아보니 점화식으로 하면 된다더라.그래도 이해가 안되서 5번째까지 직접 써보니 이해가 됐다. 11726번123456789101112131415a = int(input()) # 점화식은 a[n] = a[n - 1] + a[n - 2] 이다# 하지만 피보나치 수열과 다르게 시작은 1번쨰부터 1, 2로 시작한다# 새로 놓여질 블럭이 세로로 세워지면 a[n - 1]의 경우의수,# 새로 놓여질 블럭이 앞에 블럭과 가로로 세워지면 2칸 전인 a[n - 2]의 경우의수를 가진다.dp = [0, 1, 2] for i in range(2, a): dp.append((dp[i] + dp[i-1]) % 10007) print(dp[a]) Colored by Color Scripte..

예전에 풀었던 계단 오르기의 하위호환인데 왜 차례는 더 아래라 그때 고생했을까... 매우 간단하게 풀었다. 1234567891011121314151617181920l = list()for i in range(int(input())): l.append(int(input())) # dp를 위한 배열r = [(0, l[0], l[0])] for i in range(1, len(l)): r.append( ( # 0번쨰 마시는 경우는 이번꺼 합 안하고 이전 경우중 가장 큰거로 저장 max(r[i - 1]), # 1번째랑 2번째는 각각 0번쨰랑 1번쨰에서 지금 양 더해서 저장 r[i-1][0] + l[i], r[i-1][1] + l[i] ) ) # 결과print(max(r[-1]))Colored by Color S..

이번엔 소스코드가 2개다 위에 소스코드는 값을 리턴하는 방향으로 짜서 코드 길이가 최적화되있고아래는 dp에 저장해 불러오는 방향으로 만들어서 이해하기 쉽다(?) 이 문제는 역대급으로 시간초과와 틀렸습니다가 많이 났다.주인장이 겪은 큰 문제들만 나열하자면 1. 탐색이 왼쪽 오른쪽 아래쪽만 하면 되는줄 알았다이건 문제 예시가 좀 잘못했다. 구글링하며 보니까 다른사람들은 왜 위까지 탐색하지 이런 의문을 가지면서 알았다.계단은 위에서 아래로 내려와야하는거 아닌가? 라고 생각했는데 단순히 숫자만 그렇게 생각하자 였을 줄이야;;이거 때문에 틀렸습니다가 떴다.(30%에서 틀렸습니다.) 2. 종점일땐 확실하게 끊어라종점 옆에 종점보다 작은 수가 있으면 이제 숫자가 종점을 탈출한다. 이거때문에 시간초과가 떴다.(19%에..

잘 생각해보면 굳이 최소공배수 구할 필요도 없이 순서 바꿔서 최대공약수로 나누면 답이다. 1234567891011121314151617181920212223c = int(input()) inp = list(map(int, input().split(' '))) m = inp[0] for i in range(1, c): a = m b = inp[i] mi = b # 최대공약수 구하기 while a % b != 0: tmp = b b = a % b a = tmp else: mi = b # 첫번째 톱니//최대공약수, 구할 톱니//최대공약수 print(str(m // mi)+'/'+str(inp[i]//mi)) Colored by Color Scriptercs

백준은 런타임에러나 틀린거 왜 틀렸는지 알려주면 좋겠다. 원래 알고리즘 푸는게 이런건가 내가 뭘틀렸는지 뭘 고쳐야하는지도 모르고 막연하게 코딩하는것이.. 1234567891011121314151617181920c = input()a = list(map(int, input().split(' '))) # 이거때문에 런타임에러로 고생if c == '1': print(a[0])else: # 최고 수 mx = a[0] + a[1] # 현재 합 n = 0 for i in a: n += i mx = mx if mx > n else n # 만약 합이 0아래면 다음부터 다시 합함 if n

lcs는 참 이해가 안되는 알고리즘이다. 다이나믹 프로그래밍은 맞는데 보통 머리로 이딴 알고리즘을 만드려고 했던 내가 한심했다. 도데체 왜 이렇게 작동되는진 모르겠지만 구현은 했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051b = input()a = input()lcs = [[0 for i in b]]now = 0for i in range(len(a)): tmp = [0 for z in b] for j in range(len(b)): if a[i] == b[j]: # 맨 앞이 아니면 왼쪽 위에 있는 값에 +1 if not j == 0: tmp[j] = lcs[i][j-1] + 1 ..

1234567891011# 7번쨰 이상부터 i-1, i-5의 합이라는 규칙이 있다.# log 변수에 값을 저장해가며 계산한다.log = [1, 1, 1, 2, 2, 3] for i in range(int(input())): n = int(input()) # 만약 아직 탐색되지 않은 곳이면 만듦 for j in range(len(log), n+1): log.append(log[j-5] + log[j-1]) print(log[n-1]) Colored by Color Scriptercs

1초인줄 알고 어떻게 최적화할지 많이 고민하다 2초 시간제한을보고 아주 단순하게 예전에 나왔던 수를 모아 저장하는것으로 구현성공 1234567891011121314151617181920212223242526272829l = [[int(input())]]# 전에 나왔던건 기록할 필요가 없음his = set() # 1이 나올때까지 돌림while l[-1].count(1) == 0: tmp = list() for i in l[-1]: # 2로 나누어지고 예전에 나온적없으면 넣고 if i % 2 == 0: n = i // 2 if not n in his: his.add(n) tmp.append(n) # 3으로 나누어지고 예전에 나온적없으면 넣고 if i % 3 == 0: n = i // 3 if not n in..

다이나믹 프로그래밍은 반복하여 저장하는 도중 언제 어디서 필요없는 정보를 버리고 가볍게 하느냐가 관건이다. 1234567891011121314151617181920212223242526272829c = int(input())l = list() for i in range(c): # 역순으로 계산할거라 insert 사용 l.insert(0, int(input())) # 0,1,2번쨰 스텝인 현재 스텝 수를 저장r = [[0, l[0], 0]] for i in range(1, c): # 3번째 까지는 무조건 끝을 밟아야 하는 규칙때문에 수동으로 넣음 if i == 1: r.append([r[0][1], 0, r[0][1] + l[1]]) elif i == 2: r.append([r[1][2], r[1][0] ..