[백준]2156번 포도주 시식 - DP

n = int(input()) grape = [0] * (n+2) dp = [0] * (n+2) for i in range(n): grape[i]= int(input()) dp[0] = grape[0] dp[1] = grape[0]+grape[1] dp[2] = max(grape[0]+grape[1], grape[0]+grape[2], grape[1]+grape[2]) # 포도주가 3개일 경우에서 최대 값. for i in range(3, n): dp[i] = max(dp[i-2]+grape[i], dp[i-3]+grape[i-1]+grape[i], dp[i-1]) # 포도주를 마시지 않는 경우 까지 고려. print(max(dp)) 코드 설명 먼저 인덱스의 에러를 피하기 위해 n+2 길이 만큼의 gra..

→2021.02.13

SW개발/코딩테스트

[백준]10844번 쉬운 계단 수 - DP

n = int(input()) dp = [[0] * 10 for i in range(n)] # 0~9의 인덱스를 가지고, n의 자릿수를 가진 이중 리스트 초기화. dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] # 한자리 숫자일 때 미리 초기화. for i in range(1, n): for j in range(10): if j == 0: # 0이면 전 자릿수의 j+1 만 더함 dp[i][j] = dp[i - 1][j + 1] elif j == 9: # 9 이면 전 자릿수의 j-1 만 더함 dp[i][j] = dp[i - 1][j - 1] else: # 1~8 은 전 자릿수의 j-1, j+1 이 올 수 있으므로 두개를 더함 dp[i][j] = dp[i - 1][j - 1] + dp[..

→2021.02.12

SW개발/코딩테스트

[백준]1463번 1로 만들기 - DP

n = int(input()) dp = [0] * (n + 1) for i in range(2, n + 1): dp[i] = dp[i - 1] + 1 # 1로 구하는 경우. if i % 3 == 0: # 3으로 구하는 경우. dp[i] = min(dp[i], dp[i // 3] + 1) if i % 2 == 0: # 2로 구하는 경우. dp[i] = min(dp[i], dp[i // 2] + 1) print(dp[-1]) 코드 설명 n+1 만큼의 길이를 가진 dp 리스트를 생성함으로써 index 를 문제와 맞춰준다.(0 인덱스 사용 X) 값이 1을 입력 받는 경우에는 연산의 횟수가 0 이므로 반복문을 수행하지 않고 그냥 출력하게 한다. 값이 2이상인 경우에는 2 부터 n 까지 반복을 진행한다. 1을 빼는..

→2021.02.11

SW개발/코딩테스트

[백준]2579번 계단 오르기 - DP

n = int(input()) stair = [0 for i in range(301)] # 계단의 최대 수 300 개 point = [0 for i in range(301)] # 계단이 3개 이하일 경우, 인덱스 에러를 방지하기 위해 0으로 초기 for i in range(n): stair[i] = int(input()) point[0] = stair[0] point[1] = stair[0] + stair[1] point[2] = max(stair[0] + stair[2], stair[1] + stair[2]) # 무조건 3번째 계단을 밟아야 하므로 0,2 와 1,2 중 큰거로 저장 for i in range(3, n): # 2칸 올라온 경우 전 계단은 신경 안씀, 1칸만 올라온 경우 연속 3칸 올라오지..

→2021.02.10

SW개발/코딩테스트

[백준]1932번 정수 삼각형 - DP

n = int(input()) num = [] for i in range(n): num.append(list(map(int, input().split()))) for i in range(n-1, 0, -1): for j in range(len(num[i-1])): num[i-1][j] += max(num[i][j], num[i][j+1]) print(num[0][0]) 코드 설명 먼저 주어진 삼각형 모양의 수를 입력을 받는다. 삼각형의 아래부분 부터 반복문을 시작한다. 내부 반복문은 층의 수만큼 반복한다. 위층에 있는 수와 아래 층의 왼쪽, 오른쪽의 수에서 더한 값이 큰 값을 선택한다. 끝까지 반복하면 num[0][0] 리스트에 가장 큰 값이 저장되어 있다. Point : 아래부터 시작하여 위로 가는 b..

→2021.02.09

SW개발/코딩테스트

[백준]1149번 RGB거리 - DP

n = int(input()) cost = [] for i in range(n): cost.append(list(map(int, input().split()))) for i in range(1, n): cost[i][0] += min(cost[i-1][1], cost[i-1][2]) # 선택할 수 있는 i-1(이전 값)에서 작은 것을 누적시켜 더함 cost[i][1] += min(cost[i-1][0], cost[i-1][2]) cost[i][2] += min(cost[i-1][0], cost[i-1][1]) print(min(cost[-1])) 코드 설명 각 집을 RGB로 칠하는 비용을 먼저 리스트에 저장한다. 그 후 반복문을 돌면서 R, G, B 각각 칠하는 비용을 누적시켜 구한다. 마지막에 저장된 ..

→2021.02.08

SW개발/코딩테스트

[백준]9461번 파도반 수열 - DP

n = int(input()) length = [] for i in range(n): case = int(input()) tri = [1, 1, 1] if case >= 3: for i in range(3, case): tri.append(tri[i - 3] + tri[i - 2]) print(tri[-1]) 코드 설명 3번째까지의 초기 값을 tri 리스트에 저장하여 준다. 3이상의 경우가 나올때는 점화식을 이용해 값을 구해준다. 1 -> 1 -> 1 -> 2-> 2 -> 3 -> 4 -> 5 -> 7 -> 9 -> 12 -> 16 과 같은 형태로 계속 늘어난다. 유심히 살펴보면 i 번째의 길이는 i-3 + i-2 의 값임을 유추할 수 있다. 이를 활용해 점화식을 세울 수 있다. Point : 수가 증가..

→2021.02.07

SW개발/코딩테스트

[백준]1904번 01타일 - DP

n = int(input()) dp = [1, 2, 3] if n

→2021.02.06

SW개발/코딩테스트

[백준]9184번 신나는 함수 실행 - DP

dp = [[[0] * 21 for i in range(21)] for i in range(21)] # 값 저장을 위한 3차원 리스트 def w(a, b, c): if a 20: return w(20, 20, 20) if dp[a][b][c] != 0: # 값이 기억하고 있는 것 -> 바로 출력 return dp[a][b][c] if a < b and b < c: dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c) # 점화식 return dp[a][b][c] else: # otherwise dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b..

→2021.02.05

SW개발/코딩테스트

[백준]1003번 피보나치 함수 - DP

n = int(input()) for i in range(n): case = int(input()) zero = [1, 0, 1] one = [0, 1, 1] if case >= 3 : for i in range(3, case+1): zero.append(zero[i-2]+zero[i-1]) one.append(one[i-2]+one[i-1]) print(zero[case], one[case]) 코드 설명 기본적으로 피보나치 수의 3번째 까지는 0과 1이 등장한 횟수로 초기화하여 준다. 3이상의 숫자가 나올 경우 피보나치의 점화식을 이용하여 zero, one 리스트에 값을 추가하여 준다. Point : DP 이론을 통하여 빠른 시간내에 구할 수 있는 문제이다. 값을 기억하면서 다음 계산에 이용하는 방식이..

→2021.02.04

티스토리툴바