[백준/DP] 1146번 지그재그 서기 (C++)

문제

---

풀이

아 진짜 짱나는 문제였다... 풀이 방법을 떠올리지도 못하고 검색해서 풀이 이해하는데도 시간이 꽤 걸렸다.. 근데 해답이라고 보이는 코드가 메모이제이션을 쓰지 않고 그냥 재귀로 푸는 것 같았다. 그래서 더 헷갈렸던 것 같다. 게다가 같은 코드를 자바로 하면 시간초과가 뜨고 C++로 하면 0ms로 실행이 되어서 일단 C++로 제출했다.

그리고 내 나름대로 DP를 적용해서 다시 풀이를 해보는 중인데, 생각만큼 쉽지 않아서 완전 짱난다... 그래서 일단 다른 DP 문제들부터 익히고 다시 돌아올 것이다.. 딱 기다려..

시간초과가 떴지만 로직은 동일한 자바 코드

import java.io.*;

public class Main {

    private static final int INITIAL_VALUE = -1;
    private static final int MOD = 1000000;

    private static BufferedReader br;
    private static BufferedWriter bw;

    private static int n;
    private static int[][] dp = new int[100][100];

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        initParams();
        int answer = Math.max(calcAnswer(), 1);
        bw.append(Integer.toString(answer));

        br.close();
        bw.close();
    }

    private static void initParams() throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < dp.length; i++)
            for (int j = 0; j < dp.length; j++)
                dp[i][j] = INITIAL_VALUE;
    }

    private static int calcAnswer() {
        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer += dp(i, n - i - 1) % MOD;
            answer += dp(n - i - 1, i) % MOD;
        }
        return answer % MOD;
    }

    private static int dp(int left, int right) {
        if (left + right == 0) return 1;
        if (dp[left][right] != INITIAL_VALUE) return dp[left][right];

        int result = 0;
        if (right == 0) return result;
        for (int i = 0; i < right; i++)
            result += dp(right - i - 1, left + i) % MOD;
        return result % MOD;
    }
}

백준에서 통과하는 C++ 코드

#include<bits/stdc++.h>
using namespace std;

const int MOD = 1'000'000;
int n, dp[100][100];

int count(int left, int right){
	if(left + right == 0) return 1;
	int &ret = dp[left][right];
	if(ret != -1) return ret;

	ret = 0;
	if(right == 0) return ret;
	for(int i=0; i<right; i++)
		ret += count(right-1-i, left+i) % MOD;
	return ret % MOD;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	if(n==1){
		cout << 1;
		return 0;
	}
	memset(dp, -1, sizeof(dp));
	int ans = 0;
	for(int i=0; i<n; ++i){
		ans += count(i, n-i-1) % MOD;
		ans += count(n-i-1, i) % MOD;
	}
	cout << ans % MOD;
}

---

참고

백준 문제풀이 - 1146 지그재그 서기
백준 1146 지그재그 서기 문제풀이#DP