[Java] 백준 18858번. 훈련소로 가는 날 (골드3)

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

 

 

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

18858번: 훈련소로 가는 날

 

1. 이해 (5분) - 3분

문제 자체는 길지 않았지만, 이해하는데는 시간이 필요했습니다.

non-산 이라는 처음 보는 단어가 있어 머릿속으로 그려보는데 조금 어려움이 있었습니다.

몇 번을 다시 읽고 문제에서 주어진 '산'이라는 개념이 잡혀 풀이를 구상했습니다.

2. 계획 (5분) - 1분

풀이방법은 간단했습니다. non-산 이 되려면, 즉 산이 없으려면 문제에서 설명하듯 A1<A2>A3 형태의 부분수열이 없어야합니다. 이 말은 즉 A1 -> A2로 갈때 가능한 3가지 경우 (A2가 A1보다 크거나, 같거나 작거나)를 두번 거치며 생기는 9가지 경우의 수 중에서 하나의 경우가 막힌다는 뜻입니다.

가능한 방법의 갯수를 구해야하므로 DP형태로 이전 단계에서 가능한 방법의 수를 가지고 다음 단계를 구합니다.

이때 초기 데이터는 이전 턴에서 변화가 없었다를 1씩 넣어주고 이 후 상승이 가능한 경우, 하강이 가능한 경우를 계산해서 다음 데이터에 넣어주는 식으로 구현했습니다.

3. 검증 (5분) - 1분

제가 구상한 풀이방법에서는 가능한 이전 상태의 수 M개의 데이터를 기억하고 이를 토대로 N번 가능한 경우의 수를 계산합니다. 따라서 연산은 대력 MN번 일어날 것이고, 문제에서 입력의 범위가 100과 1000으로 주어졌기때문에 10만번이면 충분히 시간안에 정답이 나올것이라고 생각했습니다.

메모리적인 측면에서도 딱히 문제가 생길 부분이 보이지 않았습니다.

4. 풀이 (30분) - 19분

구상한 풀이방법을 토대로 코드를 작성했습니다.

 

5. 채점, 디버깅 (+30여분)

풀이자체는 시간이 많이 걸리지 않았지만... 

구현 과정에서 반대방향으로 돌아가는 반복문과 입력 데이터가 1,2인 경우 등의 예외처리 그리고 초기 구상에서 잘못생각한 부분등을 고치면서 디버깅에 시간이 꽤나 걸렸습니다.

다행히 예제로 주어진 데이터에서 오류를 발견할 수 있어서 수정해 제출했지만 예제 데이터로 알 수 없는 오류였다면 오답인지도 모른채로 제출할 뻔 했습니다...

 

추가로 디버깅을 통해 코드를 수정하다보니 + 초기에 풀이 형태를 대충 구상

이 두가지 허술함의 콤보로 코드가 상당히 난해하고 더러워졌습니다.

추후 수정하게되면 재업로드하겠습니다!

 

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

public class Main {
	static StringTokenizer st;
	static final long div = 998_244_353;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		long[][] before = new long[M + 1][3];
		long[][] now = new long[M + 1][3];

		for (int m = 1; m <= M; m++) {
			before[m][1] = 1;
		}

		long sum = 0;

		for (int n = 1; n < N; n++) {
			
			sum = 0;
			for (int m = M; m > 0; m--) {
				sum = (sum + before[m][0] + before[m][1]) % div;
				now[m-1][0] = sum;
			}
			
			sum = 0;
			now[1][1] = (before[1][0] + before[1][1] + before[1][2]) % div;
			sum = (sum + now[1][1]) % div;
			for (int m = 2; m <= M; m++) {
				now[m][2] = sum;
				now[m][1] = (before[m][0] + before[m][1] + before[m][2]) % div;
				sum = (sum + now[m][1]) % div;
			}
			
			before = now.clone();
			now = new long[M+1][3];
		}

		long answer = 0;

		for (int m = 1; m <= M; m++) {
			answer = (answer + before[m][0] + before[m][1] + before[m][2]) % div;
		}

		System.out.println(answer);
	}
}