내일은 알고리즘

루틴에 맞춰 풀어본 첫 문제입니다.

몸풀기를 할 생각으로 실버 문제를 골랐는데... 너무 빨리 끝나서 생각처럼 잘 되진 않았습니다 ㅋㅋ

문제풀이 루틴에 관한 글은

https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

숭실대학교 교내 대회에서 사용된 문제입니다.

설명도 직관적이고 DP의 개념을 잡기 좋은 문제인 것 같습니다. 

제가 짜 놓은 루틴대로 문제를 풀어보도록 하겠습니다.

1. 이해 (5분) - 1분

설명이 워낙 간단명료한 터라 이해에는 긴 시간이 걸리지 않았습니다. 

캠퍼스를 산책하고 주어진 시간에 시작점인 정보과학관에 도착하는 경로가 몇 개인지 알아내면 됩니다.

2. 계획 (5분) - 1분

우선 문제의 캠퍼스는 생긴 것 부터 그래프와 유사합니다. 시간이 정해져 있고 경로의 개수를 찾는 것이니 BFS를 생각해 볼만도 하지만 10만 분이라는 시간 후에 무시무시하게 많은 경로를 고려하면 안 될 것 같습니다.

대신 우리는 경로의 갯수만을 구하면 되고, 경로를 알 필요는 없다는 점에 착안해서 DP를 사용해 간단하게 구현이 가능할 것 같습니다. 

비슷한 느낌의 DP 문제로는 https://www.acmicpc.net/problem/2579  [계단오르기 (실버 3)]가 있을 것 같네요.

DP가 진행되는 기준이 시간과 계단으로 다르고 이 문제 같은 경우는 순환이 가능하단 차이가 있지만... 느낌이 비슷하다고 봐주시면 될 것 같습니다. 

특정 시간에 8개의 건물에 위치하는 경로의 갯수를 각각 저장하도록 [입력받은 시간][8]의 2차원 배열을 선언해 앞 시간의 정보를 토대로 풀이해보겠습니다.

그림처럼 건물들에 번호를 매기고

처음 시간 D=0일때 가능한 경로는 0번 건물이 1

D=1일 때 가능한 경로는 1,2번 건물이 각각 1

... 이런식으로 진행해나가려고 합니다.

3. 검증 (5분) - 1분

시간의 최대치는 10만, 제 계획에선 시간 1 당 8번의 덧셈 연산만 진행되면 되니 주어진 시간 1 초안에 무난하게 통과할 것 같습니다. (시간제한 1초를 대략 1억 번의 연산으로 생각하면 됩니다.)

문제에선 정답을 10억7로 나눈 나머지를 출력하라고 했는데, 풀이 도중에 int의 크기를 넘어서는 오버플로우가 발생하기 때문입니다.

매 연산마다 나누기를 진행해주면 되지만, 제가 구상한 풀이에선 신양관, 한경직기념관이 각각 4개의 값이 더해집니다.

그럼 최대 40억의 값이 나오므로 오버플로우를 방지하기 위해 아예 long 타입으로 배열을 선언해줍시다.

주어지는 입력으로 가능한 최대 80만개의 long타입 배열이 있다면 long타입의 크기는 16Byte로 사용하는 메모리는 1280만 Byte입니다.

1MB가 약 100만 Byte이므로 12MB가량의 메모리가 필요하고, JVM을 감안해도 문제에서 주어진 512MB의 메모리 안에서 충분히 동작할 것 같습니다.

4. 풀이 (30분) - 8분

여기까지 구상한 내용으로 풀어봅니다!

코드를 작성 한 뒤 주어진 예제를 넣어 확인합니다.

입력의 최솟값인 1과 10만을 넣어 출력이 정상적으로 되는 것을 확인합니다.

(움직이지 않고 머무르는 것이 불가능하므로 입력이 1인 경우 0이 나오는 것이 당연합니다. 10만을 입력한 경우의 정답은 지금 상황에서 확신할 수 없으므로 에러가 발생하지 않는지만 확인했습니다. )

5. 채점, 디버깅 (+@)

다행히 한번에 정답으로 통과되었습니다. 

이 문제를 푸는데는 총 11분이 걸렸습니다. 

실버 1의 난이도면 코딩 테스트에서 1,2번의 앞 순위로 나오는 문제니 스타트로 나쁘지 않았습니다!

DP를 구상하고 정답이 자료형의 크기를 넘치는것만 주의하면 크게 어려울 것이 없는 문제였습니다.

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

public class Main {
	static final long div = 1_000_000_007;

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

		int D = Integer.parseInt(br.readLine());
		long[][] map = new long[D + 1][8];
		map[0][0] = 1;

		for (int d = 0; d < D; d++) {
			map[d + 1][0] = (map[d][1] + map[d][2]) % div;
			map[d + 1][1] = (map[d][0] + map[d][2] + map[d][3]) % div;
			map[d + 1][2] = (map[d][0] + map[d][1] + map[d][3] + map[d][5]) % div;
			map[d + 1][3] = (map[d][1] + map[d][2] + map[d][4] + map[d][5]) % div;
			map[d + 1][4] = (map[d][3] + map[d][5] + map[d][6]) % div;
			map[d + 1][5] = (map[d][2] + map[d][3] + map[d][4] + map[d][7]) % div;
			map[d + 1][6] = (map[d][4] + map[d][7]) % div;
			map[d + 1][7] = (map[d][5] + map[d][6]) % div;
		}

		System.out.println(map[D][0]);
	}
}

감사합니다!