문제 이해 단계 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..

문제 이해 단계 https://www.acmicpc.net/problem/15486 날짜 N과 각 날마다 할 수 있는 일 Ti와 그 일을 했을 때 버는 돈 Pi가 각각 주어진다. Ti는 그 일을 할 때마다 드는 날을 뜻하며, 그 일을 하는 동안에는 다른 일을 할 수 없다. 이런 상황일 때 돈을 최대한 벌었을 때의 수익을 구하는 문제이다. 문제 접근 단계 이해부터가 살짝 복잡했는데, N일까지 일을 해서 벌 수 있는 최대수익을 D [N]이라고 하자. 이때 유의해야 할 점은 N일까지라는 것은 N일을 포함하지 않는다. 즉 1~N-1일에 한 일만 포함하는 것이다. 이를 이용해서 1일부터 살펴보자면, 1일까지 일을 해서 번 돈은 당연히 0원일 것이고(D [1] = 0) 1일 때 일해서 번 돈은 3일이 지난 4일째의..

문제 이해 단계 https://www.acmicpc.net/problem/9465 세로가 2이고 가로가 n인 스티커가 있는데 각 스티커에는 점수가 적혀있다. 스티커를 뗄 때에는 특징이 있는데 점수를 얻는 스티커의 상하좌우에 있는 스티커는 더 이상 사용 할 수 없다. 이러한 상황일 때, 얻을 수 있는 점수의 최댓값을 구하는 문제 문제 접근 단계 해당 문제를 풀기 위해서 예제로 처음부터 시뮬레이션을 돌려보도록 하겠다. 시작값 50일 때 움직일 수 있는 칸 목록이다. 이렇듯 사실상 왼쪽과 아래에 있는 10,30을 제외하면 다 움직일 수 있는 것으로 보인다. 하지만 우리는 스티커 점수의 최댓값을 구하는 것이다. 이렇듯 100, 20,10은 50뿐만 아니라 다른 수에서 접근할 수 있다. 즉 굳이 50에서 바로 접..