글 읽기 - 접근 방법..

shp9408 5년 전 0

안녕하세요 DP 접근 방법에 대해 여쭤보고싶습니다.

우선 상태를 4가지로 나눠서

S -> 올바른 괄호열

[1] -> ()S

[2] -> S()

[3] -> (S)

[4] -> ()S()

이렇게 나누고

d[i][1] = d[i-2][1] + d[i-2][3]; -> i 길이고 ()S 이런 모양일 경우 = i-2 길이고 ()S 모양인 경우 + i-2 길이고 (S) 모양인 경우 ..

d[i][2] = d[i-2][2] + d[i-2][3];

d[i][3] = d[i-2][1] +d[i-2][2] + d[i-2][3]+ d[i-2][4];

d[i][4] = d[i-4][1] +d[i-4][2]+d[i-4][3]+ d[i-4][4];

이런식으로 접근했는데

바보같은 접근법인가여?

// 10422번
// 괄호     
// DP

import java.util.Scanner;
public class BJ10422 {
	static final long mod = 1000000007;
	static long[][] d = new long[5001][5];
	static long[] d2 = new long[5001];
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int t = stdIn.nextInt();
		dp();
		for(int i=0;i<t;i++) {
			int n = stdIn.nextInt();
			long sum = 0;
			for(int j=1;j<=4;j++) {
				sum += d[n][j];
				sum %= mod;
			}
			System.out.println(sum);
		}
	}
    
	// 처음에 시도했던 방법 
	static void dp() {
		d[2][4] = 1;
		d[4][3] = 1;
		d[4][4] = 1;
		for(int i = 6;i<=5000;i+=2) {
			
			// [1] ()S
			// [2] S()
			// [3] (S)
			// [4] ()S()
			d[i][1] = d[i-2][1] + d[i-2][3]; 
			d[i][2] = d[i-2][2] + d[i-2][3];
			d[i][3] = d[i-2][1] +d[i-2][2] + d[i-2][3]+ d[i-2][4];
			d[i][4] = d[i-4][1] +d[i-4][2]+d[i-4][3]+ d[i-4][4];
			
			d[i][1]%=mod;
			d[i][2]%=mod;
			d[i][3]%=mod;
			d[i][4]%=mod;
		}
	}
}

djm03178 5년 전 0

문제를 맞히셨다면 채점 현황이나 맞은 사람 탭에서 문제를 공개한 사람들의 코드를 볼 수 있습니다. 길이가 짧은 코드를 보면 대체로 더 간략한 식을 사용하고 있지 않을까요?

shp9408 5년 전 0

아 이렇게 접근한 사람은 못본거같아서요 ㅠㅠ 감사합니다

xman 4년 전 0

접근 방법을 모르시겠으면 카탈란 수 를 검색해보세요.

많은 문제가 같은 풀이로 풀리고 (의미가 같고)

심지어 생성함수가 있어서 O(1) 구할 수 도 있어요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

접근 방법..

shp9408 5년 전 0

djm03178 5년 전 0

shp9408 5년 전 0

xman 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말