본문 바로가기

분류 전체보기53

[Python] 백준 2156번:포도주 시식 / 문제 풀이, 설명 [Python] 백준 2156번:포도주 시식 / 문제 풀이, 설명 º 코드 times = int(input()) #1인 경우 if times==1: print(int(input())) #1보다 클 경우 else: a = [0]+[int(input()) for _ in range(times)] dp = [0,a[1],a[1]+a[2]] for i in range(3,times+1): dp.append(max(dp[i-1],dp[i-3]+a[i-1]+a[i],dp[i-2]+a[i])) print(dp[times]) º 풀이 1. 풀이 과정 동적 계획법 문제를 풀면서 우리는 N까지의 최대값을 구할 때 (N-1), (N-2) 등 N보다 작은 수의 경우를 활용해왔다. 그 과정에서 점화식을 유도해내 N일 때 값을 .. 2022. 10. 29.
[Python] 백준 10844번:쉬운 계단 수 / 문제 풀이, 설명 [Python] 백준 10844번:쉬운 계단 수 / 문제 풀이, 설명 º 코드 N = int(input()) dp = [[0,1,1,1,1,1,1,1,1,1] for _ in range(N+1)] for i in range(2,N+1): for j in range(10): if j == 0: dp[i][0] = dp[i-1][1] elif j == 9: dp[i][9] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N])%10**9) º 풀이 1. 풀이 과정 N이 2일 때 맨 뒤에 0이 오는 경우 : 01 (1개) 1이 오는 경우 : 21 (1개) 2가 오는 경우 : 12,32 (2개) 즉 2가 올려면 앞에서 1과 3이 나와.. 2022. 10. 26.
[Python] 백준 1463번:1로 만들기 / 문제 풀이, 설명 [Python] 백준 1463번:1로 만들기 / 문제 풀이, 설명 º 코드 n = int(input()) dp = [0 for _ in range(n+1)] for i in range(2, n+1): # 1 빼는 경우 dp[i] = dp[i-1] + 1 # 2로 나누는 경우 if i%2 == 0: dp[i] = min(dp[i], dp[i//2]+1) # 3으로 나누는 경우 if i%3 == 0: dp[i] = min(dp[i], dp[i//3]+1) print(dp[n]) º 풀이 1. 풀이 과정 문제에서는 메모이제이션 기법을 사용하라고 10 -> 9 -> 3 -> 1과 같은 힌트를 주고 있다. 10의 연산 최솟값을 구할 때 9의 최솟값을 이용한다는 것을 알 수 있다. DP 문제에서는 계속해서 i의 횟.. 2022. 10. 26.
[Python] 백준 2579번:계단 오르기 / 문제 풀이, 설명 [Python] 백준 2579번:계단 오르기 / 문제 풀이, 설명 º 코드 times = int(input()) a = [int(input()) for _ in range(times)] # 1층 if times == 1: print(a[0]) # 2층 elif times == 2: print(a[0]+a[1]) #3층 이상일 경우 else: dp = [a[0],a[0]+a[1],max(a[1]+a[2],a[0]+a[2])] for i in range(3,times): dp.append(max(dp[i-3]+a[i-1],dp[i-2]) + a[i]) print(dp[-1]) º 풀이 1. 풀이 과정 규칙 한 번에 한 계단 or 두 계단 연속 세 개 밟기 X 도착은 반드시 밟음 알고리즘 층의 값을 a 리스트.. 2022. 10. 25.

티스토리툴바