문제 이해 단계 N개의 물건이 주어지고 각 물건에는 무게(W)와 가치(V)가 주어진다. 최대 K만큼 들 수 있을 때, 가질 수 있는 가치의 최댓값을 구하는 문제 문제 접근 단계 이 알고리즘의 문제는 이름에서 유추해 볼 수 있듯이 배낭 알고리즘이라는 DP 알고리즘 기법 쪽에서는 좀 유명한? 그런 알고리즘이다. 우선 여기서 주어지는 변수는 무게(W), 가치(V) 총 2가지가 있다. 이 두 가지 값은 모두 변하는 값이고, 가치의 최댓값을 구하는 데에 분명 영향을 줄 것이다. 즉, 점화식은 W, V를 이용한 2차원배열로 만들어질 가능성이 높다. 이제 이 점을 유의하면서 예제를 가지고 생각해 보자!! 무게 가치 6 13 4 8 3 6 5 12 이를 위에서 아래로 순차적으로 탐색한다고 가정한다. 그러니까 무게 순으..

문제 이해 단계 n가지의 동전이 있고, 그 동전에는 각각의 가치가 있다. 그리고 그 동전들을 가지고 합이 k원을 만들어야 한다. 이때 경우의 수가 총 몇 가지가 나오는지 계산하는 문제이다. 문제 접근 단계 음 일단, 늘 그렇듯 감이 오지 않으니 예제 케이스를 가지고 나열을 해보자. 여기는 K를 기준으로 K가 1~6까지 한번 해보자 1 -> 1 1+1 / 2 -> 2 1+1+1 / 2+1 -> 2 1+1+1+1 / 2+1+1 / 2+2 -> 3 1+1+1+1+1 / 2+1+1+1 / 2+2+1 / +5 -> 4 1+1+1+1+1+1 / 2+1+1+1+1 / 2+2+1+1 / 2+2+2 / 5+1 -> 5 이런 식으로의 조합이 나온다. 이를 한번 하나의 동전끼리의 관점으로 묶어보자. 일단 K가 6일 때를 살..

문제 이해 단계 N개의 돌이 있고 마지막 돌에 도착해야 한다. 1 ~ N-1개의 돌에 정보가 주어지는데 특이한 점은 작은 점프/큰 점프가 드는 에너지가 다르다. 그리고 엄청 큰 점프는 딱 한 번만 가능하다. 이러한 조건에서 에너지를 최소한만 들여 마지막 돌에 도착해야 한다. 문제 접근 단계 전형적인 DP문제인지는 모르겠지만, 이런 DP문제를 전에 많이 풀어봐서 내 눈에는 DP문제인지 바로 보였다. 왜냐하면 Top-Bottom 방식으로 생각해 보면 구조가 보이기 때문이다. 그림으로 한번 살펴보자. 돌이 나열되어 있고, 중간에 아무런 돌 X(파란색)를 잡는다고 생각해 보자. 그렇다면 돌 X에 도달할 수 있는 경우는 어떻게 나올까? 이런 식으로 총 3가지 경우밖에 나오지 않을 것이다. 확대해서 말하면, 모든 ..

문제 이해 단계 https://www.acmicpc.net/problem/11660 NxN 크기의 맵이 주어지고, 시작 좌표와 끝좌표가 주어진다. 시작 좌표와 끝좌표를 네모를 친다고 상상하고 그 선에 닿거나 안에 있는 수들의 합을 구하는 문제이다. 문제 접근 단계 문제는 굉장히 BFS나 DFS로 풀기 좋게 생겼다. 하지만 함정일 수도 있으니 조건을 한번 읽어보자. N이 최대 1024개이고, 테스트 케이스 M이 100,000개까지 이다. NxN이기 때문에 1024x1024 대략 1,000,000개인데 최악의 경우 모든 수를 찾아봐야 한다. 그리고 M이 100,000번 할 경우, 100,000 x 1,000,000,000인데.. 음 아무리 봐도 시간초과가 뜰 거 같아서 BFS나 DFS는 아니다. 아무리 고민..

문제 이해 단계 n가지의 동전이 주어지고 그 동전에는 각각의 가치가 있다. 그 동전들을 활용하여 합을 k원으로 만든다. 이때 동전을 최소한으로 사용할 때 드는 개수를 구하는 문제. (동전은 충분히 많다는 가정) 문제 접근 단계 일단 아무런 감도 잡히지 않으니까, 예제로 어느 정도 나열을 해보자. k = 1 ~ 15 일 때까지 쭉 나열해 보면 1 / 1 + 1 / 1 + 1 + 1 / 1 + 1 + 1 + 1 5 / 5 + 1 / 5 + 1 + 1 / 5 + 1 + 1 + 1 5 + 1 + 1 + 1 + 1 / 5 + 5 / 5 + 5 + 1 12 / 12 + 1 / 12 + 1 + 1 / 5 + 5 + 5 이런 식으로 하여 k = 15일 때, 답은 5 + 5 + 5로 3이 된다. 어느 정도 규칙이 보이기..

문제 이해 단계 인접한 수(양쪽에 있는 수)랑 차이가 딱 1씩만 나는 수를 계단 수라고 한다. 자릿수 N이 주어질 때, 총 몇 가지 경우의 수가 나오는지 구하는 문제이다. 문제 접근 단계 이 문제를 들었을 때는 전혀 감이 잡히지 않았기 때문에 일단 두 자리 계단수부터 계속 써봤다. N = 2 10 / 21 / 32 / 43 / 54 / 65 / 76 / 87 / 98 12 / 23 / 34 / 45 / 56 / 67 / 78 / 89 N = 3 101 / 121 / 123 / 212 / 232/ 234 / 343 / 345 454 / 456 / 565 / 567 /... / 898 / 987 / 989 1. 연속적인 숫자가 나타난다. 2. 경우의 수에 영향을 주는 것은 끝자리에 어떤 수가 오느냐이다. 3..

문제 이해 단계 포도주 n개가 주어지고 순서대로 1부터 n까지의 번호가 붙여진다. 1번 포도주부터 순서대로 마시는데 연속해서 3잔을 마실수는 없다. 그리고 각 포도주에는 점수가 있고, 가장 많은 점수를 구하는 경우의 수를 구하는 문제 문제 접근 단계 이 문제에서 핵심 조건은 3잔을 연속해서 마실 수 없다는 조건이다. 그렇기 때문에 이 점을 중심으로 풀이를 생각했다. 이전에 계단 오르기란 문제를 풀었는데, 문제가 유사한 느낌이 들어서 이것도 DP로 접근해 보면 되지 않을까? 싶었다. 임의의 포도주 위치 N을 잡고 해당 포도주를 중심으로 식을 세워보기로 했다. 선택한 포도주를 N이라고 했을 때, 포도주 N-2와 N-1와의 관계를 살펴보자. 2개까지만 살펴보는 이유는, 3잔을 연속해서 마실 수 없기 때문에 그..

문제 이해 단계 정수 n이 주어지면, 그냥 1,2,3 합의 조합으로 경우의 수를 구한다. 순서가 바뀌는 것도 다른 경우의 수로 취급한다. 문제 접근 단계 N이 1일 때부터 하나씩 살펴보겠다. N = 1 -> 1개 - 1 N = 2 ->2개 - 1 + 1 - 2 N = 3 -> 4개 - 1 + 1 + 1 - 1 + 2 - 2 + 1 - 3 N = 4 -> 7개 - 1 + 1 + 1 + 1 - 1 + 1 + 2 - 1 + 2 + 1 - 2 + 1 + 1 - 2 + 2 - 1 + 3 - 3 + 1 N = 5 -> 13개 - 1 + 1 + 1 + 1 + 1 - 1 + 1 + 1 + 2 - 1 + 1 + 2 + 1 - 1 + 2 + 1 + 1 - 2 + 1 + 1 + 1 - 1 + 2 + 2 - 2 + 1 + 2..