[BOJ 백준] 내려가기(2096) C++, Java

링크 : https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

문제 설명 : 

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

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

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

 

입력 : 

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

 

출력 : 

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

 

예제 입력 : 

3
1 2 3
4 5 6
4 9 0

 

예제 출력 : 

18 6

 

 

접근법 : 

1) 어떻게 풀 것인가?

N이 10만이므로 DFS나 BFS 등의 완전탐색은 불가능하다.

 

그런데 문제에서 나온 그림을 보다보면 특징이 보인다.

 

세로 열을 각각 1, 2, 3번이라고 할 때,

1번 열은 바로 윗칸의 1번, 2번 열에서만 내려올 수 있고,

2번 열은 3개 열 모두에서 내려올 수 있으며

3번 열은 바로 윗칸의 2번, 3번 열에서만 내려올 수 있다.

 

최댓값을 구한다고 가정할때, 이를 점화식으로 세우면

D[높이][1번열] = D[높이-1][1번열] , D[높이-1][2번열] 의 최댓값

D[높이][1번열] = D[높이-1][1번열] , D[높이-1][2번열], D[높이-1][3번열]의 최댓값

D[높이][3번열] = D[높이-1][3번열] , D[높이-1][2번열] 의 최댓값

 

으로 구할 수 있다. 

기본적인 DP(Dynamic Programming), 동적계획법 문제로 자세한  구현은 아래 Java 코드 참조.

 

2) 시간복잡도

N번 입력 받으면서 모든 로직을 처리하기 때문에 O(N)

(Java 기준 360ms)

 

3) 공간복잡도

int로 수십만개 배열을 선언해도 10MB 미만.

100만개 int = 4Bytes * 100만 = 400만 Bytes = 약 3.8MBytes

 

4) 풀면서 놓쳤던점

maxMap, minMap 복사 붙여넣기 중 변수가 많아 중간에 변수 하나를 안 바꿈.

 

5) 이 문제를 통해 얻어갈 것

DP의 기본적 활용.

기본함수 Oveloading으로 구현.

 

C++ 코드 :

// 내려가기 2096 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>


using namespace std;

int N, minAns, maxAns;
//int map[100000 + 3][3];			// 입력값
int minMap[100000 + 3][3];		// 최댓값 저장
int maxMap[100000 + 3][3];		// 최솟값 저장

int big(int a, int b) {
	if (a > b) return a;
	return b;
}

int small(int a, int b) {
	if (a < b) return a;
	return b;
}

int main() {
	// 입력받으면서 처리
	//freopen("input.txt", "r", stdin);

	scanf("%d", &N);

	int input1, input2, input3;
	for (int i = 1; i <= N; i++) {
		// 1. 지도에 차례대로 입력
		scanf("%d %d %d", &input1, &input2, &input3);

		// 2. maxMap 현재높이의 최댓값을 갱신
		// 2-1.  가장 왼쪽 자리 계산
		maxMap[i][0] = big(maxMap[i - 1][0], maxMap[i - 1][1]);
		maxMap[i][0] += input1;

		// 2-2.  가운데 자리 계산
		maxMap[i][1] = big(big(maxMap[i - 1][0], maxMap[i - 1][1]), maxMap[i - 1][2]);
		maxMap[i][1] += input2;

		// 2-3.  가장 오른쪽 자리 계산
		maxMap[i][2] = big(maxMap[i - 1][1], maxMap[i - 1][2]);
		maxMap[i][2] += input3;

		// 3. minMap도 maxMap과 동일하게 갱신
		minMap[i][0] = small(minMap[i - 1][0], minMap[i - 1][1]);
		minMap[i][0] += input1;
		minMap[i][1] = small(small(minMap[i - 1][0], minMap[i - 1][1]), minMap[i - 1][2]);
		minMap[i][1] += input2;
		minMap[i][2] = small(minMap[i - 1][1], minMap[i - 1][2]);
		minMap[i][2] += input3;
	}

	maxAns = big(big(maxMap[N][0], maxMap[N][1]), maxMap[N][2]);
	minAns = small(small(minMap[N][0], minMap[N][1]), minMap[N][2]);

	printf("%d %d", maxAns, minAns);

	return 0;
}

#endif

 

Java 코드 :

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

// 내려가기 백준 2096
public class Main {
		
	static int N, max, min;			// N 줄의 개수, max 출력할 최댓값, min 출력할 최솟값
	static int[][] map;				// 숫자가 써있는 지도
	static int[][] maxMap;			// 최댓값들을 가지고 내려오는 경우 기록
	static int[][] minMap;			// 최솟값들을 가지고 내려오는 경우 기록
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st; 
		
		// N, L 입력
		N = Integer.parseInt(br.readLine());
		
		map = new int [N+1][3];
		maxMap = new int [N+1][3];
		minMap = new int [N+1][3];
		
		for (int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			
			// 1. 차례대로 지도에 입력받음
			map[i][0] = Integer.parseInt(st.nextToken());	
			map[i][1] = Integer.parseInt(st.nextToken());
			map[i][2] = Integer.parseInt(st.nextToken());
			
			// 2. maxMap 현재높이의 최댓값을 갱신
			// 2-1. 가장 왼쪽 자리는 바로 윗칸과 가운데 칸에서만 
			// 올 수 있으므로 둘 중에 큰 값을 현재 입력값에 더 함
			maxMap[i][0] = big(maxMap[i-1][0], maxMap[i-1][1]);
			maxMap[i][0] += map[i][0];
			
			// 2-2. 가운데 자리는 모든 칸에서 내려올 수 있으므로 
			// 세 칸 중에 큰 값에 현재 입력값을 더 함
			maxMap[i][1] = big(maxMap[i-1][0],maxMap[i-1][1],maxMap[i-1][2]);
			maxMap[i][1] += map[i][1];

			// 2-3. 가장 오른쪽 자리는 바로 윗칸과 가운데 칸에서만 
			// 올 수 있으므로 둘 중에 큰 값을 현재 입력값에 더 함
			maxMap[i][2] = big(maxMap[i-1][2], maxMap[i-1][1]);
			maxMap[i][2] += map[i][2];
			
			// 3. minMap의 경우 maxMap과 같은 로직으로 처리
			minMap[i][0] = small(minMap[i-1][0], minMap[i-1][1]);
			minMap[i][0] += map[i][0];
			
			minMap[i][1] = small(minMap[i-1][0],minMap[i-1][1],minMap[i-1][2]);
			minMap[i][1] += map[i][1];

			minMap[i][2] = small(minMap[i-1][2], minMap[i-1][1]);
			minMap[i][2] += map[i][2];
		}
		max = big(maxMap[N][0], maxMap[N][1], maxMap[N][2]);
		min = small(minMap[N][0], minMap[N][1], minMap[N][2]);
		
		bw.write(String.valueOf(max)+" "+String.valueOf(min));
		bw.flush();
		bw.close();
		br.close();
	}
	
	static int big(int a, int b) {
		if (a>b) return a;
		return b;
	}
	static int small(int a, int b) {
		if (a<b) return a;
		return b;
	}
	static int big(int a, int b, int c) {
		if (a>b) return big(a,c);
		return big(b,c);
	}
	static int small(int a, int b, int c) {
		if (a<b) return small(a,c);
		return small(b,c);
	}
}