Coding Test/DP

가방 문제 (냅색 알고리즘)

""" 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치 한 종류의 보석을 여러 번 가방에 담을 수 있 다는 뜻입니다. 가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다. 첫 번째 줄은 보석 종류의 개수, 가방에 담을 수 있는 무게의 한계값 두 번째 줄부터 각 보석의 무게와 가치 4 11 5 12 3 8 6 14 4 8 """ import sys input=sys.stdin.readline n,m=map(int, input().split()) d=[0]*(m+1..

알리바바와 40인의 도둑 (Bottom-Up, Top-Down)

bottom up """ 알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1,1)격자에서 (N,N)까지 가는데 드는 에너지의 최소량 만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면 3 2 5 2 3 4 6 5 2 (1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다. 5 3 7 2 1 9 5 8 3 9 2 5 3 1 2 3 5 4 3 2 1 1 7 5 ..

최대 선 연결하기

분석 최대 부분 증가수열 분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 karla.tistory.com 풀이 """ 왼쪽의 번호와 오른쪽의 번호, 같은 번호끼리 선으로 연결 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열 오른쪽의 번호 정보가 위부터 아래 순서 서로 선이 겹치지 않고 최대 몇 개의 선 연결? 자연수 N(1

가장 높은 탑 쌓기

분석 최대 부분 증가수열 분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 karla.tistory.com 풀이 """ 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 ..

최대 부분 증가수열

분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS Longest Increasing karla.tistory.com [14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색) 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,..

[2579] 계단오르기

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net """ 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다. 각 계..

계단오르기 (Top-Down : 메모이제이션)

분석 0: return d[len] if len == 1 or len == 2: return len else: d[len] = dfs(len-1) + dfs(len-2) return d[len] print(dfs(n))

돌다리 건너기(Bottom-Up)

분석 개울을 완전히 건너려면 n번째 돌에 도착하는 것이 아니라 n번째 돌 다음에 나오는 땅에 도착해야 함 ⇢ n+2 풀이 """ 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지 """ n=int(input()) d=[0]*(n+2) d[1]=1 d[2]=2 for i in range(3, n+2): d[i]=d[i-1]+d[i-2] print(d[n+1])

네트워크 선자르기 (Bottom-Up, Top-Down)

bottom up """ 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 5가지 방법을 생각할 수 있습니다 1) 1m+1m+1m+1m 2) 2m+1m+1m 3) 1m+2m+1m 4) 1m+1m+2m 5) 2m+2m 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법? 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. """ # Bottom-Up n=int(input()) d=[0]*(n+1) d[1]=1 d[2]=2 for i in range(3,n+1): d[i]=d[i-1]+d[i-2] print(d) print(d[n]) top down n=int(input()) d=[0]*(n+1) d[1]=1 d[2]..

[2775] 부녀회장이 될테야

2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net """ a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k(1 ≤ k), 두 번째 줄에 정수 n(n ≤ 14) """ import sys input=sys.stdin.readline d=[[0 for j in range(15)] for i in ra..