내일은 알고리즘

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

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

1. 이해 (5분) - 2분

01knapsack 유형의 문제입니다. 워낙 유명한 DP문제라 따로 설명은 하지 않겠습니다.

풀이방법은 간단합니다. 우선 어떤 동전의 값이 V이라고 하면 당연히 V금액을 만드는것이 가능합니다.

그리고 만약 M이라는 금액을 만드는 방법이 있다면 우리는 V짜리 동전 하나를 더해 간단히 M+V를 만들 수 있습니다.

2. 계획 (5분) - 2분

위에서 이해한 개념을 바탕으로 계획을 세워봅시다.

사용가능한 동전의 값들을 입력받고, 크기 M+1짜리 배열을 만듭니다.

우리는 이 배열에 0원부터 순차적으로 그 금액에 가능한 가짓수를 구하고 최종적으로 M원을 만들 수 있는 가짓수를 구할것입니다.

동전의 갯수 N만큼 반복해야하는 작업은 이렇습니다.

1. V짜리 동전을 가지고 금액 V를 만드는건 당연히 가능하다. (1가지 방법)

2. 만약 M이라는 금액을 만드는 방법이 X개 있다면, 그 X가지 방법에 V짜리 동전을 더해 M+V금액을 만들 수 있다. (X가지 방법) 

이 두가지 작업을 마치면 최종적으로 주어진 동전들로 M원을 만들 수 있는 방법의 수를 구할 수 있습니다.

3. 검증 (5분) - 1분

만약 중복조합같은 방식으로 문제를 풀려고 했다면 문제가 생겼겠지만, 구상한 방식에서 M짜리 배열의 크기는 1만에 불과하고 동전과 테스트케이스도 20,10개이므로 시간초과가 발생하지는 않을 것 같습니다.

4. 풀이 (30분) - 13분

파이썬을 사용했고 문제의 풀이방법만 알고 있다면 간단히 작성가능한 코드라 금방 끝났습니다.

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

첫 제출에서 런타임에러가 발생했습니다! 동전의 값어치와 금액 M 사이에 대소관계가 없어 발생한 Index에러였습니다.

(만약 만들 금액이 30원인데, 100원짜리, 500원짜리 동전을 사용하려고 하면..? DP배열의 index를 넘어간다!) 

동전의 값어치가 금액보다 클때 반복문을 통과하는 조건문을 만들어주어 통과했습니다.

import sys

T = int(sys.stdin.readline())
sb = ""

for t in range(T):
    N = int(sys.stdin.readline())
    coin = list(map(int, sys.stdin.readline().split(' ')))
    M = int(sys.stdin.readline())
    dp = [0] * (M + 1)

    for n in range(N):
        dis = coin[n]
        if(dis > M):
            continue
        dp[dis] += 1
        
        for i in range(dis+1, M+1):
            dp[i] += dp[i-dis]

    sb += str(dp[M]) + "\n"

print(sb)

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

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

https://nodingco.tistory.com/30 의 시리즈 문제입니다.

1. 이해 (5분) - 1분

A와 B 문제와 언뜻 보면 똑같아보이는 문제입니다. 

하지만 조금 생각해보면 풀이를 위한 접근 방식이 전혀 다른걸 알 수 있습니다. 

앞의 문제에선 연산을 통한 결과가 맨 뒤 알파벳으로 나타나서 역순으로 따라가기만 하면 문제의 풀이가 가능하지만, 해당 문제에선 알파벳을 먼저 붙이고 뒤집기 때문에 맨 뒤 알파벳이 어떤 연산을 통해 나온 것인지 여러 경우가 생깁니다.

대신 문자열의 형태를 보고 어느정도 경우를 좁힐 수 있고 문자열의 길이도 앞 문제보다 훨씬 작습니다.

2. 계획 (5분) - 3분

재귀를 통해 뒷 문자열을 만들기 위해 가능한 경우를 역으로 되짚어갑니다.

대신 두가지 경우를 매 번 탐색하는게 아니라, 맨 뒷 문자가 A거나 맨 앞 문자가 B일때만 탐색합니다.

(1번 연산이 진행되면 문자열의 맨 뒤는 무조건 A, 2번 연산이 진행되면 맨 앞이 무조건 B)

그렇게 줄인 문자열의 길이가 앞의 문자열과 같아지면 두 문자열이 같은지, 즉 문제의 조건이 가능한지를 체크하고 그 결과를 저장합니다. 이때 True False에 따라 재귀문을 끝내는 조건을 움직여서 가능여부가 한 번 찾아지면 덮어씌워지지 않게했습니다.

3. 검증 (5분) - 1분

검증내용은 A와B 1번 문제와 유사하기때문에 패스하겠습니다.

4. 풀이 (30분) - 17분

재귀문 구현 부분은 조금 신경썼지만, 문자열을 조정하는 부분은 오히려 앞 문제보다 쉽게 구현 할 수 있었습니다.

5. 채점, 디버깅 

다행히 이번에도 한 번에 통과했습니다. 감사합니다!

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

public class Main {
	static int N;
	static char[] S;

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

		S = br.readLine().toCharArray();
		char[] T = br.readLine().toCharArray();

		N = S.length;

		makeS(T, T.length);

		if (N == 100) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}

	static void makeS(char[] T, int l) {
		if (l < N) {
			return;
		}
		if (l == N) {
			N = (checkS(T)) ? 100 : N;
			return;
		}

		if (T[l - 1] == 'A') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[i];
			}
			makeS(newT, l - 1);
		}

		if (T[0] == 'B') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[l - 1 - i];
			}
			makeS(newT, l - 1);
		}
	}

	static boolean checkS(char[] T) {
		for (int n = 0; n < N; n++) {
			if (T[n] != S[n]) {
				return false;
			}
		}
		return true;
	}
}

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

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

1. 이해 (5분) - 2분

원리를 깨달으면 간단한 시뮬레이션 문제입니다.

다만, 문자열 관련해서 코드를 작성할 이해도가 필요할 것 같습니다.

문제는 간단명료합니다. 앞의 문자열에 두 가지 연산을 적용해서 뒤 문자열을 만들 수 있는지를 찾습니다.

간단히 생각하면 앞의 문자에 두가지 연산을 계속 적용해서 가능한 모든 경우의 수를 볼 수도 있겠지만... 

S의 길이가 1이고, T의 길이가 1000이라면? 2^1000가지 경우를 탐색해야 하니 어마어마한 일이겠죠. 

대신 연산의 조건을 파악하고 완성된 문자열에서 거꾸로 짚어가는 식으로 가부를 판단하려고 합니다.

2. 계획 (5분) - 4분

문자열에 적용한 연산 두가지는 모두 뒤쪽에 알파벳을 하나 더 붙입니다.

즉 최종결과에서 가장 뒤에 있는 알파벳은 이전에 적용된 연산이 무엇이었는지를 알려줍니다.

두 번째 문자열이 앞의 문자열보다 더 긴 길이만큼 연산을 거꾸로 적용하면 앞의 문자열과 같은 길이의 가능한 문자열이 나오게 되고 이 문자열을 앞의 문자열과 비교해서 가부를 판단할 수 있습니다.

문자열을 실제로 뒤집어서 풀이해도 되지만 저는 dir라는 boolean타입 변수를 하나 선언해서 투포인터 식으로 앞과 뒤에서 문자열을 줄여가는 방식으로 코드를 작성했습니다.

3. 검증 (5분) - 1분

시간복잡도나 메모리에서 문제가 생길 부분은 없을 것 같고, 구상한 대로 잘 풀이된다면 코드도 문제없이 작동할 겁니다.

4. 풀이 (30분) - 25분

문제의 이해와 계획은 금방 끝났지만 코드 작성에선 시간을 꽤 사용했습니다. 

반복문을 복잡하게 사용하다 보니 디버깅을 사용해서 제대로 동작하는지 검증을 철저히 했습니다.

5. 채점, 디버깅

다행히 제출은 한 번에 통과했습니다!

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

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

		char[] s1 = br.readLine().toCharArray();
		char[] s2 = br.readLine().toCharArray();

		int N = s2.length - s1.length;

		int front = 0, back = s2.length - 1;
		boolean dir = true;

		for (int n = 0; n < N; n++) {
			if (dir) {
				if (s2[back] == 'A') {
					back--;
				} else {
					back--;
					dir = false;
				}
			} else {
				if (s2[front] == 'A') {
					front++;
				} else {
					front++;
					dir = true;
				}
			}
		}

		boolean answer = true;

		if (dir) {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[front + n]) {
					answer = false;
					break;
				}
			}
		} else {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[back - n]) {
					answer = false;
					break;
				}
			}
		}

		if (answer) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
}

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

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

JAVA로 푼 문제를 Python으로 다시 작성한 문제입니다.

풀이방법과 주의사항, JAVA 정답 코드를 보고 싶으신 분은 아래 링크를 확인해주세요!

https://nodingco.tistory.com/28

import sys

N,M = map(int, sys.stdin.readline().split(' '))
staffs = list(map(int, sys.stdin.readline().split(' ')))

left = 0
right = min(staffs) * M

while(left+1 < right):
    center = (left + right)//2
    balloon = 0

    for n in range(N):
        balloon += center//staffs[n]
    
    if(balloon >= M):
        right = center
    else :
        left = center

print(right)

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

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

1. 이해 (5분) - 1분

문제도 깔끔하고 이해에 어려운 부분도 없어 금방 이해를 마쳤습니다.

정답이 가능한 범위가 무척 넓은데 여기서 이분 탐색 문제임을 유추했습니다. 

(최악의 경우 스태프 1명이 100만분 마다 풍선 하나를 만들고, 이를 100만 개 불어야 하면.... 1조가 정답이다!) 

2. 계획 (5분) - 1분

문제를 이해한 대로 이분탐색을 통해 풀이할 계획을 세웠습니다.

이분 탐색에선 초기값을 잡는 것이 중요한데, 정답의 최댓값은 가장 빨리 풍선을 부는 스태프가 전부 부는 경우보다 작기 때문에 그 값을 최댓값으로 놓았습니다.

최솟값과 최댓값 사이의 중간값을 잡고, 이 값이 정답이 가능한 수인지를 확인합니다.

중간값을 각 스태프들이 풍선을 부는데 걸리는 시간으로 나누면 그 시간에 스태프들이 불 수 있는 풍선의 개수가 나오고 그 값을 전부 합치면 이 시간에 가능한 풍선의 개수가 나옵니다! 

풍선의 갯수를 주어진 M과 비교해서 크거나 같으면 정답이 중간값이거나 더 아래에 존재하므로 이분 탐색의 최댓값을 중간값으로 바꾸고 풍선이 부족하면 중간값 위에 정답이 존재하므로 최솟값을 중간값으로 바꿔줍니다.

3. 검증 (5분) - 3분

이분탐색 문제는 기본적으로 정답의 범위가 크기 때문에 오버플로우가 자주 발생합니다.

본 문제에서도 int의 범위는 넘을것이 딱 보였기 때문에 문제 전체에서 long을 사용하기로 했습니다.

(JAVA 언어의 long은 C, C++ 등의 longlong과 같습니다.)

4. 풀이 (30분) - 8분

이분탐색 코드는 생각해내기가 어렵지 코드량과 작성 자체는 어렵지 않기 때문에 금방 작성을 마쳤습니다.

하지만 이분탐색의 마수가 또다시 저를 괴롭히니...

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

여러 번의 오답을 맞으면서 디버깅 시간이 길어졌습니다.

문제 풀이의 접근과 코드의 논리에는 문제가 없으나, 이분 탐색의 양 극단의 값 중에서 정답을 고르는 부분에 문제가 있어 예외가 발생하는 것 같았습니다. (테스트 케이스 62%쯤에서 오답 처리되었습니다.)

검색을 통해 유익한 글을 찾아... 이분 탐색을 다시 이해하고 코드를 제출해 통과했습니다.

핵심 로직은 건드린 게 없으니, 예상대로 정답을 고르는 부분에서 문제가 있었던 것 같습니다.

https://www.acmicpc.net/blog/view/109

상당히 유익한 글이고 이분 탐색 문제 풀이에서 발생하는 오답을 잡아주기 때문에 저와 비슷한 어려움을 겪으시는 분들은 꼭 읽어보시길 추천드립니다.

구현은 쉽지만 오류 찾기가 어려운 이분 탐색 문제였습니다. 감사합니다!

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

public class Main {
	static StringTokenizer st;

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

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

		st = new StringTokenizer(br.readLine());
		long min = Integer.MAX_VALUE;
		for (int n = 0; n < N; n++) {
			staffs[n] = Integer.parseInt(st.nextToken());
			min = Math.min(min, staffs[n]);
		}
		
		long left = 0;
		long right = min * M;
		
		while(left+1 < right) {
			long center = (left + right)/2;
			long balloon = 0;
			
			for (int n = 0; n < N; n++) {
				balloon += (center / staffs[n]);
			}
			
			if(balloon >= M) {
				right = center;
			}else {
				left = center;
			}
		}
		
		System.out.println(right);
	}
}

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

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

1. 이해 (5분) - 1분

문제에서 제시하는 조건은 30의 배수이지만, 사실상 3의 배수라고 생각을 해도 무방합니다.

3의 배수가 갖는 특징은 자릿수의 숫자를 모두 더하면 3의 배수가 나온다는 점입니다.

3, 6, 9, 12(3), 15(6)... 10진법에서 올림연산이 발생할때 3의 경우는 무조건 1만큼이 부족하기 때문에 앞의 자릿수는 1이 오르고 자기 자릿수에선 1만큼이 부족해지면서 합이 유지되는겁니다.

2. 계획 (5분) - 1분

문제에선 3의 배수가 아닌 30의 배수를 요구했으므로, 최소한 한개의 0이 필요합니다.

또한 가장 큰 수를 출력하라고 했으니 각 자리의 숫자들을 내림차순으로 정렬해 출력할 필요도 있겠네요.

다만 이 모든 계산은 이렇게 만들어진 수가 30의 배수일 경우, 즉 각 자릿수의 합이 3의 배수일 때만 해주면 됩니다.

3. 검증 (5분) - 1분

예외가 발생할 경우는 0 같은 특이한 수가 입력될때일텐데요, 조건에서 숫자가 0으로 시작하지 않는다고 하니 문제되지 않을것 같습니다.

각 자리의 숫자들을 내림차순으로 정렬한 수(만들 수 있는 가장 큰 수)도 3의 배수가 맞을까요?

예시를 떠올려보면 12345이나 54321이나 전부 3의 배수입니다! 각 자릿수의 합이 3의 배수기만 하면 전부 3의 배수인게 확실합니다.

4. 풀이 (30분) - 10분

오랜만에 Python을 사용하다보니 살짝 버벅였지만 작성에 크게 어려운 부분은 없었습니다.

짧은 코드인데도 시간이 꽤 걸렸네요.

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

3의 배수가 갖는 특징을 알고 Python 언어를 알면 쉽게 풀 수 있는 문제여서 한번에 통과했습니다.

문제 풀이에는 총 15분 가량이 걸렸습니다.

정답코드입니다.

N = list(input())
N = sorted(N, reverse=True)

if N[-1] != '0' :
    print(-1)
else:
    sum = 0
    for i in N:
        sum += int(i)
    if sum % 3 != 0 :
        print(-1)
    else :
        print(''.join(N))

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

https://www.acmicpc.net/problem/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);
	}
}

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

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

문제풀이 루틴에 관한 글은

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]);
	}
}

감사합니다!