1. 문제
2096번: 내려가기
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
www.acmicpc.net
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
2. 풀이
min[0]은 이전 값, min[1]은 현재값을 저장한다. max 배열도 동일하다.
먼저 min[1]과 max[1]에 입력받은 수를 저장한다.
[1][0]은 윗줄의 첫번째, 두번째 칸 중에서 골라야 한다. 골라서 min[1][0]에 더한다.
[1][1]은 윗줄 전부에서 골라야 한다.
[1][2]는 윗줄 두번째, 세번째 칸 중에서 골라서 min[1][2]에 더한다.
입력과 탐색이 다 끝났다면 첫번째 줄 중 가장 작은 값, 가장 큰 값을 골라 출력한다.
import java.io.*;
import java.util.*;
public class BOJ_2096_내려가기2 {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int[][] min = new int[2][3];
int[][] max = new int[2][3];
StringTokenizer st;
for(int i=1;i<=N;i++){
st = new StringTokenizer(in.readLine());
for(int j=0;j<3;j++){
min[1][j] = max[1][j] = Integer.parseInt(st.nextToken());
}
min[1][0] += Math.min(min[0][0], min[0][1]);
max[1][0] += Math.max(max[0][0], max[0][1]);
min[1][1] += Math.min(Math.min(min[0][0], min[0][1]), min[0][2]);
max[1][1] += Math.max(Math.max(max[0][0], max[0][1]), max[0][2]);
min[1][2] += Math.min(min[0][1], min[0][2]);
max[1][2] += Math.max(max[0][1], max[0][2]);
for(int j=0;j<3;j++){
min[0][j] = min[1][j];
max[0][j] = max[1][j];
}
}
int ans1 = Math.max(max[0][0], Math.max(max[0][1], max[0][2]));
int ans2 = Math.min(min[0][0], Math.min(min[0][1], min[0][2]));
System.out.println(ans1 +" "+ ans2);
}
}
3. 결과
[N][3]칸 배열을 만들어서 dp로 했더니 메모리를 가장 많이 썼다.
자바는 해당되지 않지만 다른 언어는 메모리 4MB제한이라 조금 더 적게 사용할 수 있는 방법이 뭘지 생각해보다가 두 가지 배열을 가지고 스위칭해가면서 푸는 방식을 발견했다.
위의 세 풀이가 전부 그런 식인데 엄청나게 큰 차이가 나진 않는다. (입력하는 데 이미 메모리를 많이 소비해서 그럴까?)
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 1769 3의 배수 - JAVA (0) | 2023.06.06 |
---|---|
[BOJ] 4358 생태학 - JAVA (0) | 2023.06.06 |
[BOJ] 1013 Contact - JAVA (0) | 2023.06.04 |
[BOJ] 5582 공통 부분 문자열 - JAVA (0) | 2023.06.04 |
[BOJ] 25206 너의 평점은 - JAVA (1) | 2023.06.03 |
댓글