본문 바로가기

전체 글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.
[Python] 백준 1932번:정수 삼각형 / 문제 풀이, 설명 [Python] 백준 1932번:정수 삼각형 / 문제 풀이, 설명 º 코드 times = int(input()) ar = [list(map(int,input().split())) for _ in range(times)] k=2 for i in range(1,times): for j in range(k): if j == 0: ar[i][j] = ar[i][j] + ar[i-1][j] elif i == j: ar[i][j] = ar[i][j] + ar[i-1][j-1] else: ar[i][j] = max(ar[i-1][j-1],ar[i-1][j])+ar[i][j] k+=1 print(max(ar[times-1])) º 풀이 1. 풀이 과정 양 끝의 수는 바로 위에 수밖에 받을 수 없다. 그리고 양 끝이 아.. 2022. 10. 24.
[Python] 백준 1912번:연속합 / 문제 풀이, 설명 [Python] 백준 1912번:연속합 / 문제 풀이, 설명 º 코드 times = int(input()) num = list(map(int,input().split())) #합을 저장하기 위한 리스트 생성 dp = [num[0]] # num[0] ~ num[times-1] 까지 알고리즘에 따라 합을 구해 append하는 for문 for i in range(1,times): if dp[i-1]>0: dp.append(dp[i-1] + num[i]) else: dp.append(num[i]) print(max(dp)) º 풀이 1. 전체적인 코드 풀이 입력받은 수의 첫 번째부터 마지막까지 순차적으로 더하는데 합을 dp에 저장하고 앞선 dp가 0보다 클 때만 num의 다음 수를 더해서 dp에 저장한다. 아닐.. 2022. 10. 23.
갤럭시 캠퍼스 스토어 - 갤럭시, 학생 할인 갤럭시 캠퍼스 스토어 - 갤럭시, 학생 할인 º 갤럭시 캠퍼스 스토어, 갤럭시 유저들을 위한 최고의 선택 º 다양한 혜택이 존재하지만 갤럭시 유저들은 " 갤럭시 캠퍼스 스토어 "를 이용하는 것이 혜택이 가장 많다. 그 이유는 아래에서 알아보자. 1. 갤럭시 캠퍼스 데이 한정 수량 상품 고속 충전기, 노트북 등 매달 상품은 바뀌지만 네이버 페이 1만 P와 함께 충전기를 판매하는 경우가 많다. 19,900에 고속 충전기를 구매하면 네이버 페이 1만 P를 받으니 환급받는 기분이다. 충전기는 매진이 빨리 되는 편이다. 스페셜 경품 이벤트 확률은 낮지만 되기만 하면 공짜로 제품을 얻을 수 있는 경품 이벤트도 매일 열리고 있다. 조건은 상품 구매 1개 이상인 경우가 많다. 고속 충전기가 없는 분들은 갤캠스 데이에 .. 2022. 10. 18.
[Python] 백준 9461번:파도반 수열 / 문제 풀이, 설명 [Python] 백준 9461번:파도반 수열 / 문제 풀이, 설명 º 코드 def Dp(n): tri = [1,1,1] if n>=4: for i in range(3,n+1): tri.append(tri[i-2] + tri[i-3]) return tri[n-1] n = int(input()) for _ in range(n): print(Dp(int(input()))) n은 1부터 시작하니 tri 인덱스와 맞추기 위해 -1을 해야한다. º 풀이 과정 ( 1,1,1,2,2,3,4,5,7,9 - - - ) 이렇게 숫자가 늘어선다 수의 규칙을 잘 보면 4번째부터 f(4) = f(2)+f(1) / f(5) = f(3) + f(2) / f(6) = f(4) + f(3) 이렇게 된다. 결국 N이 4이상 일 때 f(N.. 2022. 10. 18.

티스토리툴바