[백준] code.plus(다이나믹 프로그래밍,JAVA)10422번, 괄호

문제 링크

10422번: 괄호

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

이 문제에 핵심은

 

1. 길이 L개인 괄호 문자열의 종류를 구합니다.

2. 괄호 문자열의 개수를 1,000,000,007을 나눈 나머지를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 L에 대한 정보를 저장합니다.

 

2. 괄호 조합의 개수를 구해서 DP[]에 저장합니다.

 

3. DP[L]의 값을 결과로 출력합니다.

 

 

DP[L]의 형태

길이가 L일 때 괄호 문자열의 종류의 개수가 저장됩니다.

 

 

괄호 문자열 종류 구하는 과정

 

※L이 홀수일 때에는 괄호 문자열을 만들 수 없기 때문에 모두 0으로 처리합니다.

 

L(0) : " "

L(2) : ()

L(4) : (()), ()()

L(6) : ()()(), ((())), (())(), ()(()), (()())

L(8) : ()()()(), (())(()), ()((())), ((()))()....

 

규칙.

괄호가 나올 수 있는 과정은 하나의 괄호가 존재하고 안에 괄호의 종류, 밖에 괄호의 종류 조합으로 만들 수 있습니다.

Ex.

L : 8

DP[6] × DP[0] = 5 × 1 = 5

DP[4] × DP[2] = 2 × 1 = 2

DP[2] × DP[4] = 1 × 2 = 2

DP[0] × DP[6] = 1 × 5 = 5

 

DP[8] = 5 + 2 + 2 + 5 = 14

 

 

예제입력 1.

 

1. 입력되는 L에 대한 정보를 저장합니다.

 

T = 3

 

L : 1, 2, 4

 

2. 괄호 조합의 개수를 구해서 DP[]에 저장합니다.

 

위에서 설명한 방식대로 DP를 구성합니다.

	0	1	2	3	4
DP[]	1	0	1	0	2

 

3. DP[L]의 값을 결과로 출력합니다.

 

DP[1] = 0

DP[2] = 1

DP[4] = 2

 

DP[1], DP[2], DP[4]을 순차적으로 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• init함수를 실행하여 1...5000까지의 DP값을 저장합니다.
• T개의 DP[L] 값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• init는 2중 for문으로 각 괄호 문자열의 개수를 DP에 저장합니다.
• init는 1..5000까지의 DP값을 구해서 저장하였습니다.

 

import java.util.*;
import java.io.*;
public class Main {
    static int T, MUL = 1000000007;	//나머지를 구하기 위해 나누는 값
    static long[] DP = new long[5001];
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        T = Integer.parseInt(br.readLine());
        init();	//DP구성
        //T개의 DP[L]의 값 BufferedWriter 저장
        for(int i=0;i<T;i++){
            int L = Integer.parseInt(br.readLine());
            bw.write(DP[L] + "\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //DP구성하는 함수
    static void init(){
        DP[0] = DP[2] = 1;	//초기값 설정
        //DP[] 구하는 방식 적용 후 저장
        for(int i=4;i<=5000;i+=2){
            for(int j=0;j<i;j+=2){
                DP[i] += DP[j] * DP[i-j-2];
                DP[i] %= MUL;
            }
        }
    }
}