본문 바로가기

Algorithm(BOJ, Python)/Dynamic Programing56

[백준_1912] 연속합 python 처음에 dp정의 자체를 잘못 설정했다. 처음 내 아이디어는 dp[i]를 i번째까지 최대 연속 합으로 설정하였으나, 이중for문에 걸려 시간 초과 문제가 발생했다. 이후 구글링을 통해 다른 아이디어를 찾아보니 dp[i]를 i번째까지 왔을 때, arr[i]와 dp[i-1] + arr[i] 중 최댓값으로 설정하는 정의를 통해 해결하는 방법을 찾았다. 처음엔 잘 이해가 가지 않았으나, 찬찬히 생각해보니 이와 같이 dp를 채우고 나중에 출력 시 전체에 max값을 출력 해 주면 되는 것이였다. # n 입력 n = int(input()) # arr 입력 arr = list(map(int, input().split())) # dp 설계 dp = [ 0 for _ in range(n) ] # 초기설정 dp[0] = ar.. 2022. 7. 5.
[백준_11053] 가장 긴 증가하는 부분수열 python 생각외로 되게 간단하게 풀렸다. 역시 커피한잔하면서 백준문제풀면 훨씬 나은 듯 하다. 점화식이 항상 깔끔하게 한줄식으로만 나오지 않을수도 있다는 교훈을 얻게 해준 문제였다. # n 입력 n = int(input()) # a 입력 a = list(map(int, input().split())) # dp 설계 dp = [ 0 for _ in range(1000) ] # 초기설정 dp[0] = 1 # dp 채워넣기 for i in range(1, n): # dp 최댓값 설정 M = 0 for j in range(i): # 이전까지 더 작은 수 중에 dp 값이 더 큰수 를 찾으면 if a[j] M: # dp 최댓 값 갱신 M = dp[j] # 채워넣기 dp[i] = M + 1 .. 2022. 7. 4.
[백준_9095] 1,2,3 더하기 python 좀 이상하리만큼 규칙의 근본이 보이지 않은 문제였다. 그냥 다포기하고 쭉 늘여뜨려보니 이게 어디서부터 오는 규칙인지는 모르겠는데 전전전 + 전전 + 전 = 현재 라는 발견(?)을 해냈다. 풀고서도 찜찜하다 ㅋㅋ # dp 설계 dp = [ 0 for _ in range(11) ] # 초기 설정 dp[1] = 1 dp[2] = 2 dp[3] = 4 # dp채우기 for i in range(4, 11): dp[i] = dp[i-3] + dp[i-2] + dp[i-1] # t 입력 t = int(input()) for _ in range(t): # n 입력 n = int(input()) # 출력 print(dp[n]) 2022. 7. 3.
[백준_9465] 스티커 python 분명 풀기 시작했을땐 12시였는데,, # t 입력 t = int(input()) for _ in range(t): # n 입력 n = int(input()) # sticker s = [] # score for _ in range(2): s.append(list(map(int, input().split()))) # n == 1 if n == 1: print(max(s[0][0], s[1][0])) # n >= 2 else: # dp 설정 dp = [ [0,0] for _ in range(100001) ] # 초기설정 dp[1][0] = s[0][0] dp[1][1] = s[1][0] dp[2][0] = s[1][0] + s[0][1] dp[2][1] = s[0][0] + s[1][1] # dp 채워넣기 f.. 2022. 7. 3.
[백준_2579] 계단오르기 python 실버3 문제라고 얕잡아봤다가 큰코다쳤다. 2칸전? 1칸전을 기준으로 이차원 배열로 생각하는 dp문제인가?하고 생각했는데, 생각보다 쉽지가 않았다. 결국 구글링을 통해 아이디어를 얻었다. 결론은 세칸 전과 두칸 전을 기준으로 나눠 큰 값을 취하는 dp점화식을 통해 해결하는 것이였다. # n 입력 n = int(input()) # 계단 값 입력용 리스트 stair = [ 0 for _ in range(301) ] # 계단 값 입력 for i in range(1, n + 1): stair[i] = int(input()) # dp 설계 dp = [ 0 for _ in range(n + 1) ] # n == 1 if n == 1: print(stair[1]) # n == 2 elif n == 2: print(st.. 2022. 7. 2.
[백준_1463] 1로 만들기 python 내일 요코하마 놀러가기로 해서 12시에 미리 풀었는데, 솔브닥 업데이트 시간은 12시가 아니라 6시였다. 그리 어렵지않은 dp문제였으나, 혹자는 처음 봤을 때 그리디 문제로 오해할 수 있는 느낌이 들었다. 또한, n=1일때를 생각하지 못해 처음에는 인덱스 에러가 발생했다. 이는 예외처리로 해결했다. # n 입력 n = int(input()) # dp 설계 dp = [ 0 for _ in range(n + 1) ] # n == 1 if n == 1: print(0) # n >= 2 else: # dp 초기설정 dp[2] = 1 # dp 채워넣기 for i in range(3, n + 1): if i % 3 == 0 and i % 2 == 0: dp[i] = min(dp[i-1], dp[i//3], dp[i.. 2022. 7. 2.
[백준_1149] RGB거리 python 푸는데 한시간 이상 걸렸다. 1차원 배열로 해결하려 했다가 큰코다쳤다. 왜 그랬는지 나도 내가 이해가 안간다. 변수의 개수에 따라 배열의 개수를 늘려나가는 기초적인 개념을 까먹어선 안 될 것이다. # n 입력 n = int(input()) # cost 리스트 형성 cost = [0] for _ in range(n): cost.append(list(map(int, input().split()))) # dp설계 dp = [ [0] * 3 for _ in range(1001) ] # 초기설정 dp[1][0] = cost[1][0] dp[1][1] = cost[1][1] dp[1][2] = cost[1][2] # dp 채워넣기 for i in range(2, len(cost)): dp[i][0] = min(dp.. 2022. 7. 1.
[백준_2156] 포도주시식 python 규칙을 찾는것이 쉽지 않았다. 결국 나도 구글링을 하여 조금(?) 도움을 받았다. 틀리면 답지보고 배우는거지뭐 문제는 이후에 발생했다. 100% 채점 후 런타임에러가 뜨는 데 이유를 모르겠었다. 찬찬히 다시 살펴보니 마지막 인덱스에서 나는 오류가 아닌 n이 1이거나 2일때의 문제였다. 따라서 n이 1이거나 2일때에는 예외 처리를 해 주었다. # n 입력 n = int(input()) # table table = [0] # 와인 양 입력 for _ in range(n): wine = int(input()) table.append(wine) # n == 1일 경우 if n == 1: print(table[1]) # n == 2일 경우 elif n == 2: print(table[1] + table[2]) #.. 2022. 6. 29.
[백준_11726] 2×n 타일링 python 오늘은 뭔가 다 하기싫다. 그래서 쉬운문제 풀었다. 이런날도 있는게 아니겠나 # dp 설계 dp = [ [0] * 2 for _ in range(1001) ] # 초기설정 dp[1][0] = 0 dp[1][1] = 1 dp[2][0] = 1 dp[2][1] = 1 # dp 채워넣기 for i in range(3, 1001): dp[i][0] = dp[i-2][0] + dp[i-2][1] dp[i][1] = dp[i-1][0] + dp[i-1][1] # 입력 n = int(input()) # 출력 print(sum(dp[n]) % 10007) 2022. 6. 28.
[백준_2688] 줄어들지 않아 python 처음에 리커전으로 모든 경우의수를 조사해야하나 생각했다. 그러나 오히려 그렇게 해결하면, 각 자리수를 비교해야하며, 두자릿수 기준 00 같은 수의 처리가 애매해지는 문제가 발생해 오히려 더 귀찮아질 것 같았고 시간복잡도 측면에서 찜찜한 느낌도 들었다. 결국 결론은 2차원 배열을 이용한 dp였다. # dp 설계 dp = [ [0] * 10 for _ in range(64 + 1) ] # 초기 설정 for i in range(10): dp[1][i] = 1 for i in range(1, 65): dp[i][0] = 1 # dp 채워넣기 for i in range(2, 65): for j in range(1, 10): dp[i][j] = dp[i-1][j] + dp[i][j-1] # t 입력 t = int(.. 2022. 6. 27.
[백준_10164] 격자상의 경로 python 초등학교때 했던 길찾기 문제를 활용한 dp문제였다. 신나서 dp설계하고 점화식 세웠는데 ,,, 쨋든 내가 생각한 방법은 다음과 같다. # 입력 n, m, k= map(int, input().split()) # dp 설계 dp = [ [0] * (m + 1) for _ in range(n + 1) ] # 초기값 설정 dp[1][1] = 1 # k == 0인 경우 if k == 0: for i in range(2, m + 1): dp[1][i] = 1 for j in range(2, n + 1): dp[j][1] = 1 for i in range(2, n + 1): for j in range(2, m + 1): dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[n][m]) # k.. 2022. 6. 26.
[백준_11052] 카드 구매하기 python 모든 경우의수를 비교해봐야 한다. n = int(input()) price = list(map(int, input().split())) price_list = [0] for p in price: price_list.append(p) dp = [ 0 for _ in range(n + 1) ] dp[1] = price_list[1] for i in range(2, n+1): for j in range(1, i + 1): if dp[i] < dp[i-j] + price_list[j]: dp[i] = dp[i-j] + price_list[j] print(dp[n]) 2022. 6. 25.
[백준_2502] 떡 먹는 호랑이 python 처음 이 문제를 접했을 때, dp인 것과 점화식은 너무 분명히 보였으나, 초기 값 설정을 어떻게 해야 할지 고민에 빠졌다. dp[d-1]부터 역추적을 해야 하나 했으나, 수가 그렇게 많지 않아 전수조사를 해도 나쁘지 않겠다는 아이디어가 떠올랐다. d, k = map(int, input().split()) dp = [ 0 for _ in range(31) ] for i in range(1, k): for j in range(i, k): dp[1] = i dp[2] = j for h in range(3, d + 1): dp[h] = dp[h-1] + dp[h-2] if dp[d] == k: print(dp[1]) print(dp[2]) quit() dp = [ 0 for _ in range(31) ] 2022. 6. 23.
[백준_17271] 리그 오브 레전설 (Small) python dp를 구현함에 있어서 무지성 세보기는 참 좋은 방법인 것 같다. 다만, 내가 구하는 칸이 어디서로부터 오는지 그 근본을 잘 확인해야 한다. dp = [ [0] * 101 for _ in range(10001) ] for i in range(1, 10001): dp[i][1] = (2 ** i) for i in range(1, 10001): for j in range(1, 101): if i == j: dp[i][j] = 2 elif i j: dp[i][j] = (dp[i-j][j] + dp[i-1][j]) n, m = map(int, input().split()) pri.. 2022. 6. 22.
[백준_2225] 합분해 python dp모르겠으면 진짜 3~4개는 세어보는게 답인 것 같다. 나도모르는 규칙이 나올지도? n, k = map(int, input().split()) dp = [ [0] * 201 for _ in range(201) ] for i in range(1, 201): dp[1][i] = 1 dp[i][1] = i for i in range(2, 201): for j in range(2, 201): dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[k][n] % 1000000000) 2022. 6. 21.
[백준_10844] 쉬운 계단 수 python dp = [0 for _ in range(101)] for i in range(101): dp[i] = [0 for _ in range(10)] for i in range(1,10): dp[1][i] = 1 for i in range(2, 101): for j in range(10): if j == 0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) n = int(input()) print(sum(dp[n]) % 1000000000) 2022. 6. 20.
[백준_15990] 1, 2, 3 더하기 5 python 규칙은 쉽게 찾았다. dp라는것을 아는데 시간이 걸렸을 뿐 import sys input = sys.stdin.readline dp = [0] * 100001 for i in range(100001): dp[i] = [0,0,0] dp[1] = [1,0,0] dp[2] = [0,1,0] dp[3] = [1,1,1] for i in range(4, 100001): dp[i][0] = (dp[i-1][1] + dp[i-1][2]) %1000000009 dp[i][1] = (dp[i-2][0] + dp[i-2][2]) %1000000009 dp[i][2] = (dp[i-3][0] + dp[i-3][1]) %1000000009 t = int(input()) for _ in range(t): n = int(inp.. 2022. 6. 18.
[백준_11727] 2×n 타일링 2 python 처음에 2*2 타일을 못보고 풀어서 애좀 먹었다. dp문제를 보고 바로 dp를 언제쯤 떠올릴 수 있을까. 난 정말 코테가 싫다. # 입력 받기 n = int(input()) # dp dp = [0] * (n+1) # 초기 설정 dp[0] = 1 dp[1] = 1 for i in range(2, n+1): dp[i] = (dp[i-1] + 2*dp[i-2]) % 10007 print(dp[-1]) 2022. 6. 16.

티스토리툴바