이번엔 소스코드가 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] ..

오늘은 조금 쉬어가는날.. 1234567891011121314151617_a, _b = map(int, input().split(' ')) a, b = (_a, _b) if _a > _b else (_b, _a) mi = b while a % b != 0: tmp = b b = a % b a = tmpelse: mi = b print((_a // mi) * _b) Colored by Color Scriptercs

다이나믹 프로그래밍은 단순히 과정을 저장? 하는것으로 푸는 느낌이다.123456789101112131415161718l = list()r = list()c = int(input()) for i in range(c): l.append(list(map(int, input().split(' ')))) r.append(l[0]) for i in range(1, c): tmp = [l[i][0] + r[i - 1][0]] for j in range(1, len(l[i]) - 1): tmp.append((r[i - 1][j - 1] if r[i - 1][j]

12345678910111213141516171819# 입력값l = list()# 합용l2 = list()for i in range(int(input())): l.append(list(map(int, input().split(' ')))) # 첫번째 합은 당연히 그대로l2.append(l[0]) for i in range(1, len(l)): l2.append(list()) # 이웃하지 않은 것들중 2개중 작은것을 더함 그걸 R스타트 G스타트 B스타트 다 나눠서 3갈래로 저장 l2[i].append(l2[i-1][2] + l[i][0] if l2[i-1][1] > l2[i-1][2] else l2[i-1][1] + l[i][0]) l2[i].append(l2[i - 1][0] + l[i][1] if l2..