목록다이나믹 프로그래밍 (5)

DevLog:-)

[알고리즘][파이썬]2839-설탕 배달

문제 코드 import sys N = int(sys.stdin.readline()) dp =[0,-1,-1,1,-1,1]+[0 for i in range(N)] for i in range(6,N+1): dp[i] =-1 if(dp[i-3]!=-1 and dp[i-5]!=-1): dp[i] = min(dp[i-3]+1,dp[i-5]+1) elif(dp[i-3]!=-1): dp[i] = dp[i-3]+1 elif(dp[i-5]!=-1): dp[i] = dp[i-5]+1 print(dp[N]) 코멘트 Dp를 이용해서 풀었다. 제시된 무게를 3킬로그램과 5킬로그램 봉지로 나눌 때 봉지 수가 최소가 되도록 하는 문제이다. 제시된 무게까지 for문을 돌려서 dp리스트에 최소 개수를 계속 저장할 수 있도록 했다. 그..
알고리즘/백준 2023. 7. 17. 01:34
[알고리즘][파이썬]2579-계단오르기

문제 코드 n=int(input()) s=[int(input()) for _ in range(n)] dp=[0]*(n) # dp 리스트 if len(s)
알고리즘/백준 2023. 7. 13. 23:38
[알고리즘][파이썬]14501-퇴사

문제 1. 초기 풀이 import sys N = int(sys.stdin.readline()) li = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(N)] s =[0] for i in range(N-1,-1,-1): S = li[i][0] M = li[i][1] MAX = M if(i+S-1)>=N: li[i][1] = -1 continue for j in range(i+S,N): #해당 일자의 상담기간 이후 기간을 for문으로 돌면서 최대 금액을 찾는다. if(li[j][1] != -1 ): MAX = max(MAX, M + li[j][1]) li[i][1] = MAX #각 일자별 최대 금액으로 list를 갱신한다. s.app..
알고리즘/백준 2023. 7. 12. 23:51
[알고리즘][파이썬]1463-1로 만들기 (BFS/DP)

문제 1.BFS코드 import sys from collections import deque x = int(sys.stdin.readline().strip()) def fun(start_x): q= deque() q.append((0,start_x)) while(q): C, cur_x =q.popleft() if(cur_x==1): return C elif(cur_x!=0): if(cur_x % 3 == 0): q.append((C+1,cur_x//3)) if(cur_x % 2 == 0): q.append((C+1,cur_x//2)) q.append((C+1,cur_x-1)) print(fun(x)) #큐에 연산 횟수, 연산 결괏값을 넣어 와일문을 돌려서 1이 나올 때의 연산 횟수 반환했다. 2.DP코드..
알고리즘/백준 2023. 7. 5. 23:29
[알고리즘][파이썬]1149-RGB거리

문제 코드 import sys n = int(sys.stdin.readline()) R=[] for i in range(n): r,g,b = map(int,sys.stdin.readline().strip().split()) #strip왼쪽 공백 제거 if(i==0): RGB=[r,g,b] continue RGB = [min(RGB[1], RGB[2]) + r, min(RGB[0], RGB[2]) + g, min(RGB[0], RGB[1]) + b] print(min(RGB)) 집을 빨강,초록,파랑 중 하나의 색으로 칠해야하는데 이때 집마다 빨강,초록,파랑색을 칠하는 비용이 제공된다. i번째 집은 i+1번째 집과 색이 무조건 달라야하는 것이 특징이다. 이 문제는 DP로 풀이가 가능하다. 풀이방법 1번째 집..
알고리즘/백준 2023. 5. 14. 23:21
이전 Prev 1 Next 다음