문제 이해 단계 인접한 수(양쪽에 있는 수)랑 차이가 딱 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에서 바로 접..
문제 이해 단계 https://www.acmicpc.net/problem/1890 각 칸마다 이동해야 하는 칸 수가 적혀 있고, 가장 왼쪽 위 칸에서 오른쪽 아래 칸으로 이동해야 한다. 즉, 해당 칸에 도착했을 때 0이면 움직임이 멈춘다.(더 이상 이동하지 못하기 때문) 할 수 있는 움직임은 아래로 이동하거나 왼쪽으로 이동하거나 2가지이다. 이러한 조건일 때 가장 오른쪽 아래로 이동할 수 있는 경우의 수를 구하는 문제. 문제 접근 단계 가장 오른쪽 아래로 이동할 수 있는 경우의 수를 구하는 것이기 때문에 오른쪽 아래에서부터 역으로 출발하는 걸로 생각했다. 게임판의 크기가 NxN일 때, 마지막 칸으로 움직일 수 있는 경우는 무엇이 있을까? 그림으로 생각해 보면 이런 식이 될 것이다. 이런 식으로 마지막칸에..
문제 이해 단계 수열이 주어졌을 때 위치를 가만히 둔 채로, 오름차순으로 증가하는 부분 수열은 구한다. 그때 가장 크게 증가하는 부분수열의 길이를 구하는 문제 문제 접근 단계 문제에 나와있는 예시로 생각해 보자 10 20 10 30 20 50 1번째 수(10)에서 가장 긴 부분수열의 길이는 1이다. 2번째 수까지의 경우의 수는 3가지이다. 1. 10 - 20 (2가지) 2. 20 (1가지) 3. 10 (1가지) 이때 가장 긴 부분수열은 1번째인 2이다. 3번째 수까지의 경우의 수는 1. 10 - 20 (2가지) 2. 20 - 10 (2가지) 3. 20 ... 로 2번째보다 길어지려면 20보다 수가 높아야 하는데, 그렇지 못하므로 그대로 최대 길이는 2이다. 4번째 수까지의 경우의 수는 1. 10 - 20..
문제 이해 단계 N의 길이를 가진 수열에서 최대 K개만큼 원소를 삭제할 수 있을 때, 최대한 많이 짝수끼리 연속되게 만드는 문제이다. 그때의 개수를 구하는 문제이다. 문제 접근 단계 처음에는 1차원에다가, 짝수와 홀수를 구분하여 탐색하는 BFS를 떠올렸다. 그런데 일반적인 탐색으로 하기에는 제거할 홀수의 경우의 수가 너무 많다. 그리고 그 경우의 수를 모두 체크하기엔 너무 연산이 복잡하고 또 시간이 오래 걸린다. 또한 여기서는 어떤 시작 인덱스나 숫자를 정해주지 않아서 그것 또한 찾아야 하기 때문에 이 방법은 어울리지 않는다고 생각했다. 그다음으로 떠올린 것은 다이내믹 프로그래밍이다. 왜냐하면 이런 제한시간이 짧고, 많은 경우의 수가 있는 경우에는 충분히 가능성 있기 때문이다. 연속된 짝수를 계산하기 위..