CodeDrive

문제:

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력:

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

풀이방법:

 SCV는 최대 3개까지만 있을 수 있기 때문에 이보다 더 적은 SCV가 들어온다면 0 배열을 이어 붙여서 길이가 3인 배열로 만들어 주도록 한다. SCV는 최대 체력이 60이고, 몇번째로 공격받느냐에 따라 체력이 달라지기 때문에 60의 길이를 가지는 3차원 visited 배열을 만든다.

 이후로는 BFS를 사용하여 나올 수 있는 경우의 수를 기반으로 체력을 감소시키며 모두 0이 되는 순간이 정답이다.

문제링크:

https://www.acmicpc.net/problem/12869

문제:

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력:

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

풀이방법:

 N명의 아이들을 번호 순서대로 배치하기 위해 최소의 움직임을 구한다는 것은 LIS 문제와 같다. 가장 긴 부분 수열을 찾고, 그 수열에 속하지 않은 아이들만 움직이는 것이 최소 움직임일 것이기 때문이다.

 따라서 DP를 사용한 LIS 문제를 풀고, N에서 그 값을 빼주도록 한다.

문제링크:

https://www.acmicpc.net/problem/2631

문제:

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력:

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

풀이방법:

dfs와 DP를 같이 사용해서 이 문제를 풀었다. 기본적인 방식은 dfs를 사용해서 조건에 맞게 이동을 하며 최종 목적지까지 탐색을 한다. 그러다가 최종 목적지에 도달하면 재귀를 빠져나오면서 그 경로에 +1을 해주면서 다시 돌아오게 된다. 

이 과정을 가능한 모든 경우에 대해서 수행할 수 있기 때문에 최종적으로는 dp[0][0]에 저장되어 있는 값을 출력해주면 된다.

문제링크:

https://www.acmicpc.net/problem/1520

문제:

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력:

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

풀이방법:

 앞에서 부터 덧셈, 뺄셈을 수행하면서 0이나 20을 넘어가는 수가 발생하면 저장을 하지 않는 DP 방식으로 풀면 된다. 0~20의 배열을 생성한 뒤에 한 step이 지나갈 때마다 덧셈, 뺄셈을 한 수를 집어 넣는다. 그림으로 보면 다음과 같다.

1) 첫 행은 첫 값을 이용해 다음과 같이 초기화 한다.

2) 다음 행은 이전 행의 1 값에 대해서 덧셈과 뺄셈을 반복한다.

3) 0과 20을 넘어가는 숫자가 있다면 제외한다.

2)와 3) 과정을 반복하고, dp[n-2][numbers[n-1]]을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/5557

문제:

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력:

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력:

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

풀이방법:

 자두가 움직일 수 있는 횟수는 W로 초는 T로 고정되어 있기 때문에 열은 W이고, 행은 T인 DP 테이블을 만들어서 이 문제를 해결하도록 한다.

 계속해서 움직이지 않는 경우는 1에서만 점수가 오르기 때문에 1일때만 이전 행의 0열 값을 가져와 1을 더하도록 한다. 1번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 짝수일 때 카운트가 오르게 되고, 2번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 홀수일 때 카운트가 오르게 된다. (1번나무에서 초기에 위치하기 때문)

문제링크:

https://www.acmicpc.net/problem/2240

문제:

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력:

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력:

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)

풀이방법:

N명이 있을 때, 발생하는 경우의 수를 점화식으로 구하면 DP[N] = DP[N-1]+DP[N-2]와 같이 구할 수 있다.

그리고 VIP들 같은 경우에는 움직이지 못하기 때문에 주위 사람들과 자리 변경이 불가능하다. 따라서 양 옆을 분할한다라고 생각할 수 있다. 즉 문제에서 소개한 예시로 보면 9개의 자리가 있을 때, 4와 7에서 자리를 분할하고 있다. 이제 이 문제는 DP[3] * DP[2] * DP[2]와 같이 경우의 수를 구하면 된다.

문제링크:

https://www.acmicpc.net/problem/2302

문제:

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력:

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력:

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이방법:

www.acmicpc.net/problem/2293 의 동전 1 문제를 응용해서 풀면 된다. 이 문제에서는 k원을 만드는 경우의 수를 구하는 문제였지만, 이 문제에서는 최솟값을 구해야 한다. 따라서 동전의 가치가 최대 100,000원이므로 초기값으로 100,001원(0원은 0으로 초기화 한다.) 으로 설정하고, 작은 동전부터 사용해서 각 p원을 만들 수 있는 최소 갯수를 구하도록 한다.

 이 문제의 예시로 생각하면 다음과 같다. (1,5,12)원이 있을 때, 1원으로 15원을 만드는 방법은 다음과 같이 비교할 것이다.

 위 표는 다음 두 조건을 비교하면서 채워나갔다. 1원을 만드는 경우로 예시를 든다.

1. 현재 값을 그대로 사용한다. dp[1]

2. 0원에서 1원을 더해서 사용한다. dp[1-1]+1

3. 1과 2중 더 작은 값을 사용한다. min(dp[1],dp[1-1]+1)

즉 이를 일반화 하면 다음과 같다. min(dp[n],dp[n-c]+1), n은 현재 만들고자 하는 금액, c는 현재 사용하고 있는 동전의 가치다.

 5원을 사용하는 경우는 1~4원은 만드는 것이 불가능하므로 5원부터 반복한다.

 12원을 사용하는 경우는 1~11원은 만드는 것이 불가능하므로 12부터 반복한다.

 최종적으로는 dp[k]원이 초기화한 값에서 변경이 되었다면 dp[k]를 출력하고, 바뀌지 않았다면 -1을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/2294

문제:

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력:

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이방법:

0으로 초기화 된 DP 배열을 미로의 값에 따라 초기화 하면서 진행하면 된다.

이 문제의 예제를 통해서 설명한다. 처음에는 다음과 같이 초기화 된다.

numbers[0]의 값은 1이므로 dp[1]의 값을 업데이트한다.

numbers[1]의 값은 2이므로 dp[2]~dp[3]의 값을 업데이트한다.

numbers[2]의 값은 0이므로 넘어가고, numbers[5]까지 반복하면 아래와 같이 된다.

 만약 이미 dp[i+j]에 0이 아닌 다른 값이 초기화되어 있다면, dp[i+j]값과 dp[i]+1값 중 작은 값을 사용하도록 한다. 끝까지 진행하면 다음과 같이 된다.

 위 작업을 모두 반복했을 때, 맨 마지막 값이 0이 아닌 다른 값으로 바뀌었다면, 끝에 도달할 수 있는 것이므로 해당 값을 출력하면 되고, 아니라면 -1을 출력하도록 한다. 그리고 생각해야 하는 예외가 두가지가 있다.

 첫번째는 5 (0,0,0,1,0)과 같은 경우가 있다. 이런 경우는 if dp[i]==0 and i!=0 와 같은 조건문을 넣어서 해결해준다. 정상적으로 진행될 때, dp에 0 값은 dp[0]을 제외하고 생기면 안되기 때문이다.

 두번째는 1 (0) 이다. 이 경우에는 시작과 동시에 오른쪽 끝으로 도달한 경우이기 때문에, 마지막 출력하는 단계에서 예외처리로 0을 출력하도록 한다.

문제:

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 불어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표가 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력:

첫째 줄에 N(1<=N<=100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0,1,2,3,4,5,6,7,8,9 중의 하나가 된다.

출력:

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

풀이방법:

 가로의 길이가 세 개로 고정되어 있기 때문에 그림의 세 조건에서 파란 동그라미에 해당하는 부분들에서 값을 가져와서 최댓값과 최솟값을 계산하면 된다.

 하지만 이 문제에는 메모리 제한이 걸려 있었는데, N이 최대 100,000까지 존재하기 때문에 초기에 이 배열을 모두 초기화하고 더해나가면 메모리 초과가 발생하게 된다. 따라서 처음부터 N만큼의 배열을 초기화하지 않고, 한 줄씩 입력 받으며 최댓값과 최솟값을 바꾸어 나가도록 한다.

0번째 인덱스에서는 이전 행의 0번째와 1번째 값에만 영향을 받으며,

1번째 인덱스는 이전 행 전체에서,

2번째 인덱스는 이전 행의 1번째와 2번째 값에만 영향을 받는다.

max와 min을 사용해 각 칸을 tuple 형식으로 업데이트 했다. (max값, min값) 그리고 마지막에서는 max와 min의 key 옵션을 활용해서 전체 최대 점수와 최소 점수를 구하도록 했다.

문제링크:

www.acmicpc.net/problem/2096

문제:

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10+20+25+20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력:

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력:

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

풀이방법:

조건3인 마지막 계단을 무조건 밟아야 하기 때문에 경우의 수는 다음 2개만 존재하게 된다.

1. 마지막칸의 전칸을 밟고 마지막 칸으로 이동하는 경우

2. 마지막의 전전칸을 밟고 마지막칸을 밟는 경우

그런데 1번의 경우에는 조건2가 있기 때문에 이를 고려해 줘야 한다. 

이 것을 코드로 구현하게 되면 다음과 같다. 

1번 -> dp[n-3] + stair[n-1] + stair[n]

2번 -> dp[n-2] + stair[n]

따라서 이 둘중 max 값을 골라서 진행하면 된다.

이를 위해서 dp[0], dp[1], dp[2]를 초기화 해줬는데, 만약 계단의 개수가 이보다 적게 되면 런타임에러가 발생하게 된다.

따라서 stair를 공백의 빈 배열을 만들어도 되긴 하는데, 단순히 조건문을 추가해서 답을 구하도록 만들었다.

문제링크:

https://www.acmicpc.net/problem/2579