동적계획법4 [BOJ] 백준 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 n개의 동전의 가치가 주어질 때 동전을 원하는 대로 사용하여 k원을 만드는 경우의 수를 구하는 문제입니다. 동적 계획법 관련 문제들에서 이 문제와 유사한 문제들이 가끔 출제되며 이 문제를 잘 이해하고 풀면 0/1 배낭 문제 또한 쉽게 풀 수 있습니다. 풀이 쉽게 접근해 보기 위하여 dp [i][j]를 0~i 번째 동전을 사용하여 j원을 만들 때 적어도 한 개의 i번째 동전을 사용하는 경우의 수.. 2021. 3. 24. [BOJ] 백준 11726번: 2xn 타일링, 타일링 문제 www.acmicpc.net/submit/11726/21279055 로그인 www.acmicpc.net 타일링 문제는 동적 계획법을 접하면 입문 문제로 간단한 점화식으로 풀리는 문제입니다. 타일은 1x2 크기와 이것을 회전한 2x1 타일이 있으며, 길이 n이 주어질 때 2 x n 직사각형을 채울 수 있는 경우의 수를 찾아야 합니다. 아래는 n이 각각 1, 2, 3 인 경우를 보여줍니다. 각 경우에서 보면 빨간 블록은 이전 단계들의 블록 모양이며 파란색은 현재 단계에 새로 추가된 블록입니다. 여기까지만 보면 점화식을 d[i] = d[i-1] + d[i-2]로 유추해볼 수 있습니다. 좀더 정확하게 알아보기 위해 n이 4인 경우를 보면 n이 2인 경우 + n이 3인 경우의 합이 됩니다. 점화식은 피보나치 형태.. 2020. 9. 7. [BOJ] 백준 1014번: 컨닝 https://www.acmicpc.net/problem/1014 1014번: 컨닝 문제 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼 www.acmicpc.net 교실 정보가 주어질 때, 위의 그림처럼 컨닝이 가능해 A,C,D,E 중 한 자리라도 사람이 앉아있으면 컨닝을 방지하기 위하여 해당 자리를 앉지못하게 합니다. 위의 규칙을 만족하면서 최대한 몇명의 사람이 앉을 수 있는지 구하는 문제입니다. 저는 동적계획법으로 해결하였습니다. (입력이 10X10이므로 꽤 다양한 알고리즘으로 해결가능하다고 생각합니다.) DP[i][j] 는 i-1번째 줄에 j 상태로 앉아있을 때 i번째.. 2020. 8. 11. [BOJ] 백준 10217번: KCM Travel https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net M원 이하로 1번 도시에서 N번 도시까지 갈 수 있는 경로 중 최단시간을 요구하는 문제입니다. 두가지 방법이 있는데 저는 동적계획법으로 해결했습니다. DP[i][j] 배열을 i 도시에서 j원으로 출발할 때 n 도시까지 걸리는 최단 시간으로 정의했습니다. 주의할 점은 입력 중 출발공항과 도착공항이 같은 여러개의 티켓 정보가 들어올 수 있다는 점입니다. (이걸.. 2020. 8. 9. 이전 1 다음
