백준 2294 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 전 나의 생각 동전, 동전1에 이어서 나온 동전2 문제다. 문제 모두 동전을 이용하여 목표 가치를 만드는데에 중점을 두고 있다. 이번 문제 동전2에서는 동전1과 달리 모든 경우의 수를 구하는 것이 아닌 최소가 되는 경우를 구해야 한다. 즉, DP 점화식의 재활용이 불가능하기 때문에 새로운 점화식을 구해내야 한다. 그럼 이제 모든 경우의 수가 아닌..
알고리즘 및 자료구조/DP
백준 2011 https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 풀이 전 나의 생각 주어진 숫자를 1 = A , 2 = B... 의 조건으로 암호화해야 한다. 하지만 숫자를 암호화 했을 때 글자로 바꾸는 방법이 여러가지기 때문에 모든 경우의 수를 구해야 한다. 우선 문제에서 나온 예시인 25114를 사용하여 각 상황에 어떤 암호가 나오는지 판별해보자. 2 = B 25 = BE, Y 251 = BEA, YA 2511 = BEAA, YAA, YK, BEK (2) ->..
백준 10942 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 전 나의 생각 팰린드롬을 만들 수열에서 S번째 수부터 E번째 까지 수가 팰린드롬을 이루었다면 1, 아니라면 0을 반환한다. 그럼 우선 팰린드롬이 되기 위한 조건을 생각해봐야 한다. 백준 예제인 (1, 2, 1, 3, 1, 2, 1) 수열을 예시로 들어서 설명하면 팰린드롬의 길이가 1이라면 어떤 숫자든 팰린드롬이다. 왜냐하면 숫자 하나는 좌우반전을 해도 결국 같은 값이 나오기 때문이다. -> palindrom[i][..
백준 1915 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 전 나의 생각 0과 1이 주어진 배열값을 판단하여 정사각형의 최대 크기를 구하는 문제다. 문제를 보면 뭔가 처음부터 계속 탐색을 하면서 값을 갱신 시켜야만 될 것 같다. 그럼 우선적으로 해야 할 것은 DP가 무엇을 의미하고 어떤 값을 갱신 시킬 지 알아야한다. 1. 조건을 보면 정사각형의 최대 크기를 구해야한다. 이 말은 직사각형이 아닌 정사각형을 구해야 하니깐 한 변의 길이만 구하면 정사각형의 크기를 쉽게 구해낼 수 있다. 2. DP는 이전 값을..
백준 4883 https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 풀이 전 나의 생각 이 문제의 요점은 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 구해내는 것이다. 조건 1. N은 2보다 같거나 크거나 100000 보다 작거나 같다. 2. 정점의 비용은 정수이며, 비용의 제곱은 1000000보다 작다. 문제를 풀기위한 조건은 이와 같다. 여기서 중요한 정보는 정점의 비용이 정수라는 것이다. (정수: 0..
백준 1904 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 전 나의 생각 타일을 이용하여 2진 수열을 만드려고 한다. 하지만 0의 쓰여진 모든 타일들은 한 쌍으로 이루어진 00타일이 됐다. 이 조건을 만족하면서 자연수 N에 대해 최대로 만들 수 있는 2진 수열을 구해내야 한다. 우선 N이 1 부터 4까지 있다고 가정할 때 경우의 수를 구해보면 N = 1 -> 1 N = 2 -> 00, 11 N = 3 -> 000, 111, 100 N = 4..
백준 2293 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원이 되게하는 문제다. 우선 먼저 생각할 수 있는건 n번째의 동전을 탐색하면서 얻을 수 있는 조합을 찾아내야 한다는 것이다. 그럼 1원이 3원(k = 3)까지 증가하면서 DP값을 구한다고 가정해보자. DP[1] - 1원이 될 수 있는 방법은 '1' 한 가지 DP[2] - 2원이 될 수 있는 방법은 '1 + 1' 한 가지 DP[3] - 3원이..
백준 2302 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 풀이 전 나의 생각 N개의 극장 좌석과 M개의 VIP 좌석이 주어졌을 때 앉을 수 있는 서로 다른 방법의 가짓수를 구해야 한다. 조건 1. 일반석은 본인 자리에서 좌우로 움직일 수 있다. 2. VIP석은 움직일 수 없다. 이 조건을 만족하면서 나올 수 있는 경우들을 한 번 구해보자. 최대 자릿수가 1일 때 [1] 최대 자릿수가 2일 때 [1][2] [2][1] 최대 자릿수가 3일 때 [1][2]..
