본문 바로가기

Algorithm 💡/DP41

[백준 15989번] 1, 2, 3 더하기 4 import sysinput = sys.stdin.readlinet = int(input())dp = [1]*10001for i in range(2,10001): dp[i] += dp[i-2]for i in range(3,10001): dp[i] += dp[i-3]for i in range(t): print(dp[int(input())]) 이번 문제는 주어진 숫자를 1, 2, 3을 사용하여 만들 수 있는 경우의 수를 구하는 문제이다. 1부터 10까지의 케이스를 구하다보니 패턴이 존재할 것 같다는 예감이 들었고, DP문제라는 것을 감으로 알 수 있었다. 하지만 점화식을 찾는 것이 너무 어려워서 다른 블로그를 참고하였다. 먼저 모든 숫자는 1로만 채우는 방법이 존재하기 때문에 DP테이블을 1.. 2024. 9. 26.
[프로그래머스 Lv.3] 등굣길 def solution(m, n, puddles): # m x n 크기의 격자모양 # 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다 # 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지 # 0 1 1 1 # 1 0 1 2 # 1 1 2 4 area = [[0]*m for _ in range(n)] for x, y in puddles: area[y-1][x-1] = 1 dp = [[0]*m for _ in range(n)] for i in range(1,n): if area[i][0] == 0: .. 2024. 7. 15.
[프로그래머스 Lv.3] N으로 표현 def solution(N, number): answer = -1 if N == number: return 1 # N을 i+1번 사용했을 때 만들 수 있는 값들 dp = [set() for i in range(9)] for i in range(1,9): dp[i].add(int(str(N)*i)) for i in range(2,9): for j in range(1,i): for term1 in dp[j]: for term2 in dp[i-j]: dp[i].add(term1 + term2) dp[.. 2024. 7. 4.
[백준 2096번] 내려가기 https://www.acmicpc.net/problem/2096import sysinput = sys.stdin.readlinen = int(input())dp_max = [0]*3dp_min = [0]*3for _ in range(n): a, b, c = map(int,input().split()) temp_max = dp_max[:] temp_min = dp_min[:] for i in range(3): if i == 0: dp_max[i] = a + max(temp_max[0],temp_max[1]) dp_min[i] = a + min(temp_min[0],temp_min[1]) elif i == 1: .. 2024. 6. 28.
[백준 17404번] RGB거리 2 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net n = int(input()) costs = [list(map(int,input().split())) for _ in range(n)] answer = float("inf") for i in range(3): dp = [[float("inf")]*3 for _ in range(n+1)] dp[0][i] = costs[0][i] for j in range(1,n): dp[j][0] = min(dp[j-1][1],dp[j-1][2]) + .. 2023. 10. 1.
[백준 11659번] 구간 합 구하기 4 11659번: 구간 합 구하기 4첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 jwww.acmicpc.netn,m = map(int,input().split())numbers = list(map(int,input().split()))answers = []dp = [0]*(n+1)for i in range(1,n+1): dp[i] = dp[i-1] + numbers[i-1]for _ in range(m): i, j = map(int,input().split()) answers.append(dp[j]-dp[i-1])for answer in.. 2023. 10. 1.