알고리즘 정복 시리즈를 시작합니다!
문제
자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.
매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.
자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.
입력
첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.
출력
첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.
예제 입력1
7 2
2
1
1
2
2
1
1
예제 출력1
6
정답 비율
38.503%
문제를 풀어볼까요!
문제 분석 및 사고 회로
자두의 최대 개수를 구하려면 어떻게 해야 할까?
움직일때마다 자두를 최대로 얻을 수 있는 위치로 이동하면 된다.
알고리즘적으로 생각하면 어떻게 구현할 수 있을까?
움직이는 모든 경우의 수를 고려해서, 각 움직임에 얻을 수 있는 최대의 자두 갯수를 찾아 누적시키면 되지 않을까?라고 생각한다.
움직임이 나올 수 있는 경우를 나열해보자.
1번 나무 → 1번 나무, 1번 나무 → 2번 나무, 2번 나무 → 2번 나무, 2번 나무 → 1번 나무
총 4가지 움직임이 존재한다.
각 움직임에 얻을 수 있는 최대의 자두 갯수를 어떻게 코드로 표현할까?
한가지 예시를 통해 생각해보자.
다음 표는 백준 예시 입력에 나와있는 표이다.
이 표를 기준으로 현재 2초일때 나올 수 있는 경우를 생각해보자
우선 위치가 2가지로 나뉜다. 2초일때, 자두가 1번 위치에 있을 수도 있고, 2번 위치에 있을 수도 있다.
그 다음으로 각 위치별로 앞서 말했던 4가지 움직임을 가지기 때문에 2x4로 총 8가지의 경우의 수가 나온다.
8가지의 경우의 수가 뭔지 좀 더 디테일하게 작성해보자.(2초일 때를 기준으로 작성한다.)
(1) 2초일 때, 1번 위치에 자두가 있는 경우 - 4가지
1번 위치 - 🍎 자두를 먹는 경우
(1 - 1) 1초일 때, 1번 위치에 있다가 2초일 때, 1번 위치에 가만히 있는 경우
(1 - 2) 1초일 때, 2번 위치에 있다가 2초일 때, 1번 위치로 움직이는 경우
2번 위치
(1 - 3) 1초일 때, 2번 위치에 있다가 2초일 때, 2번 위치에 가만히 있는 경우
(1 - 4) 1초일 때, 1번 위치에 있다가 2초일 때, 2번 위치에 움직이는 경우
(2) 2초일 때, 2번 위치에 자두가 있는 경우 - 4가지
1번 위치
(2 - 1) 1초일 때, 1번 위치에 있다가 2초일 때, 2번 위치로 움직이는 경우
(2 - 2) 1초일 때, 2번 위치에 있다가 2초일 때, 2번 위치에 가만히 있는 경우
2번 위치 - 🍎 자두를 먹는 경우
(2 - 3) 1초일 때, 2번 위치에 있다가 2초일 때, 1번 위치로 움직이는 경우
(2 - 4) 1초일 때, 1번 위치에 있다가 2초일 때, 1번 위치로 가만히 있는 경우
풀이 코드
위에 설명한 부분을 코드로 구현해 보자.
public class Main {
public static int T;
public static int W;
public static int[] zadu;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
zadu = new int[T + 1]; // 0초부터가 아닌, 1초부터 시작하기 위해서
for (int i = 1; i <= T; i++) {
zadu[i] = Integer.parseInt(br.readLine());
}
// 위치 - 1아니면 2, 시간, 움직임
int[][][] dp = new int[3][T + 1][W + 2];
// 0부터 시작하면 index = -1이되서 오류가 발생
for (int i = 1; i <= T; i++) {
for (int j = 1; j <= W + 1; j++) { // 이동하는 횟수 만큼
if (zadu[i] == 1) { // T초에 자두의 위치가 1인 경우
// 1번->1번(현재위치), 2번->1번(현재위치) (자두 획득 O)
dp[1][i][j] = Math.max(dp[1][i - 1][j], dp[2][i - 1][j - 1]) + 1;
// 1번->2번(현재위치), 2번->2번(현재위치) (자두 획득 X)
dp[2][i][j] = Math.max(dp[1][i - 1][j - 1], dp[2][i - 1][j]);
} else { // T초에 자두의 위치가 2인 경우
if (i == 1 && j == 1) { // 자두는 1번 자두나무 아래에 위치 --> 2번 자두나무로 갈 수 없다.
continue;
}
// 1번->1번(현재위치), 2번->1번(현재위치) (자두 획득 X)
dp[1][i][j] = Math.max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
// 1번->2번(현재위치), 2번->2번(현재위치) (자두 획득 O)
dp[2][i][j] = Math.max(dp[1][i - 1][j - 1], dp[2][i - 1][j]) + 1;
}
}
}
int result = Integer.MIN_VALUE;
for (int i = 1; i <= W + 1; i++) {
result = Math.max(result, Math.max(dp[1][T][i], dp[2][T][i]));
}
System.out.println(result);
br.close();
}
}
코드 분석
🔎 3차원 배열을 사용해서 DP를 정의하는 이유
3차원 배열은 각 시간, 자두나무 위치, 이동 횟수로 나뉘어 진다.
시간
자두는 시간이 지나면서 떨어지기 때문에, 각 시간에서 자두를 얻을 수 있는지를 확인해야 한다.
자두나무 위치
플레이어는 1번 또는 2번 자두나무 아래에 있을 수 있고, 어느 위치에 있느냐에 따라 자두를 얻을 수 있거나 없을 수 있다. 이를 반영하기 위해 현재 위치가 필요하다.
이동 횟수
플레이어가 자두나무를 이동할 수 있는 횟수에 제한이 있다. 따라서 몇 번 이동했는지에 따라 최대 자두를 얻는 전략이 달라질 수 있다. 이동 횟수가 적으면 이동을 하지 못해 자두를 덜 획득할 수 있고, 더 많이 이동할 수 있으면 더 많은 자두를 얻을 수 있기 때문에 이동 횟수도 확인해야 한다.
🔎 이동횟수를 추적해야 하는 이유
한가지 문제 상황을 예시로 들어 보자.
자두가 떨어지는 위치는 다음과 같다고 가정한다.
| 1초 | 2초 | 3초 | 4초 | 5초 | |
| 1번 자두나무 | 🍎 | 🍎 | 🍎 | ||
| 2번 자두나무 | 🍎 | 🍎 |
각 이동 횟수에 따른 자두를 잡을 수 있는 갯수를 비교해보자.
단 각 이동횟수 별로 자두를 최대로 잡을 수 있는 경우만 보자.
이동횟수가 0번인 경우
| 1초 | 2초 | 3초 | 4초 | 5초 | |
| 1번 자두나무 | 🍎 🙆🏻♂️ | 🙆🏻♂️ | 🍎 🙆🏻♂️ | 🍎 🙆🏻♂️ | 🙆🏻♂️ |
| 2번 자두나무 | 🍎 | 🍎 |
총 3개의 자두 얻을 수 있다.
이동횟수가 1번인 경우
| 1초 | 2초 | 3초 | 4초 | 5초 | |
| 1번 자두나무 | 🍎 🙆🏻♂️ | 🙆🏻♂️ | 🍎 🙆🏻♂️ | 🍎 🙆🏻♂️ | |
| 2번 자두나무 | 🍎 | 🍎 🙆🏻♂️ |
총 4개의 자두 얻을 수 있다.
이동횟수가 2번인 경우
| 1초 | 2초 | 3초 | 4초 | 5초 | |
| 1번 자두나무 | 🍎 🙆🏻♂️ | 🍎 🙆🏻♂️ | 🍎 🙆🏻♂️ | 🙆🏻♂️ | |
| 2번 자두나무 | 🍎 🙆🏻♂️ | 🍎 |
총 4개의 자두 얻을 수 있다.
이동횟수가 3번인 경우
| 1초 | 2초 | 3초 | 4초 | 5초 | |
| 1번 자두나무 | 🍎 🙆🏻♂️ | 🍎 🙆🏻♂️ | 🍎 🙆🏻♂️ | ||
| 2번 자두나무 | 🍎 🙆🏻♂️ | 🍎 🙆🏻♂️ |
총 5개의 자두 얻을 수 있다.
이동 횟수에 따라서, 자두를 잡을 수 있는 갯수가 달라진다.
문제에서 이동 횟수가 제한이 있기 때문에 이동을 전략적으로 가져가야 한다.
즉, 이동할 수 있는 횟수를 추적해서 각 시점에서 나무를 바꾸는지, 그대로 머물러 있는지를 결정해야 한다.
각 시점에 위치를 이동하는지에 따라 이동할 수 있는 횟수가 같음에도 불구하고 받을 수 있는 자두의 갯수가 달라진다.
이동 횟수가 1번인 경우를 예시로 들어보자.
1. 5초에 이동한 경우
| 1초 | 2초 | 3초 | 4초 | 5초 | |
| 1번 자두나무 | 🍎 🙆🏻♂️ | 🙆🏻♂️ | 🍎 🙆🏻♂️ | 🍎 🙆🏻♂️ | |
| 2번 자두나무 | 🍎 | 🍎 🙆🏻♂️ |
획득할 수 있는 자두의 갯수는 4개가 된다.
2. 2초에 이동한 경우
| 1초 | 2초 | 3초 | 4초 | 5초 | |
| 1번 자두나무 | 🍎 🙆🏻♂️ | 🍎 | 🍎 | ||
| 2번 자두나무 | 🍎 🙆🏻♂️ | 🙆🏻♂️ | 🙆🏻♂️ | 🍎 🙆🏻♂️ |
획득할 수 있는 자두의 갯수는 3개가 된다.
주의할 점
배열의 인덱스를 0부터 시작하게 되면, 아래와 비슷한 모든 로직들이 인덱스 오류가 발생한다.
인덱스에 -1은 존재하지 않기 때문이다. 인덱스를 1부터 시작할 수 있도록 배열 초기 선언시 주의해준다.
dp[1][i][j] = Math.max(dp[1][i - 1][j], dp[2][i - 1][j - 1]) + 1;
T초에 자두의 위치가 2인 경우, 아래 코드와 같은 조건문도 추가해주어야 한다.
if (i == 1 && j == 1) { // 자두는 1번 자두나무 아래에 위치 --> 2번 자두나무로 갈 수 없다.
continue;
}
i와 j가 1이라는 것은 1초에 움직임이 없는 경우를 나타내는데, 문제에서 자두는 1초에 1번 자두나무 아래에 위치한다고 나와있다.
반복문을 탐색할 때, 1부터 W+1까지로 코드에 표현한 것을 볼 수 있다.
왜 이렇게 코드를 구현했을까?
for (int j = 1; j <= W + 1; j++) {
문제에서는 이동할 수 있는 최대 횟수를 말해주었다. 이 말은 곧, 이동하지 않아도 된다는 말도 포함되어 있다.
즉, 인덱스 오류와 이동횟수가 0번인 경우도 고려해주어야 하므로 j = 1인 경우는 이동하지 않은 경우라고 보는게 더 이해하기 쉽다.
결론
각 시간초마다 이동할 수 있는 모든 경우를 고려하여 DP 배열에 이전 위치를 기준으로 현재 위치에 올 수 있는 경우 중 자두을 얻을 수 있는 최댓값을 찾아서 계속해서 갱신해나간다.
제출 결과
'알고리즘' 카테고리의 다른 글
| 🙆🏻♂️ DP 너, 정복당해라 [백준 2240번 - 알약 편] (0) | 2024.09.26 |
|---|
