programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr def solution(n, money): answer = 0 dp = [[0] * (n+1) for _ in range(len(money)+1)] dp[0][0] = 1 for i in range(1, len(money)+1): for j in range(n+1): if money[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j..
programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr import copy def solution(land): answer = 0 length = len(land) dp = copy.deepcopy(land) for i in range(1, length): for j in range(4): for k in range(4): if k != j: dp[i][j] = max(dp[i][j], land[i][j] +..
programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 7 7 7 7 7 3 8 10 15 10 15 10 15 10 15 8 1 0 -> 8 1 0 -> 18 16 15 -> 18 16 15 -> 18 16 15 2 7 4 4 2 7 4 4 2 7 4 4 20 25 20 19 20 25 20 19 4 5 2 6 5 4 5 2 6 5 4 5 2 6 5 4 5 2 6 5 25 30 27 26 24 def solution(triangle): answer = 0 length = len(triangle) for ..
programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 첫번째 집을 터는 경우에 마지막 집은 인접한 경우이기 때문에 털 수 없고, 마찬가지로 마지막 집을 터는 경우 첫번째 집을 털 수 없기 때문에 두 경우로 나눠서 계산 def solution(money): answer = 0 length = len(money) dp = [0] * length # 첫번째 집을 털고, 마지막 집은 안 터는 경우 dp[0] = money[0] dp[1]..
www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net import sys N, K = map(int, sys.stdin.readline().split()) s = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] s.insert(0, [0, 0]) dp = [[0] * (K + 1) for _ in range(N+1)] for i i..
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net s1 = list(input()) s2 = list(input()) s1_len = len(s1) s2_len = len(s2) dp = [[0] * (s2_len+1) for _ in range(s1_len + 1)] for i in range(s1_len): for j in range(s2_len): if s1[i] == s2[j]: dp[i+1][..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net import sys n = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [0] * n dp[0] = seq[0] for i in range(1, n): dp[i] = max(dp[i-1] + seq[i], seq[i]) print(max(dp))
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net import sys n = int(sys.stdin.readline()) d = [list(map(int, sys.stdin.readl..