2811 알약 - 백준

알약 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

6520

4207

3252

66.941%

문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

예제 입력 1 복사

6
1
4
2
3
30
0

예제 출력 1 복사

132
1
14
2
5
3814986502092304

출처

ICPC > Regionals > North America > Rocky Mountain Regional > 2011 Rocky Mountain Regional Contest E번

• 문제를 번역한 사람: baekjoon

풀이

약이 담긴 병 N개

 

한조각을 꺼내서 반 먹고 반은 넣음 <- 이날은 W를 보냄

반 조각 꺼낸 날은 다 먹음 <- H를 보냄

서로 다른 문자열 나올 수 있는 경우의 수는 몇 개인가

 

입력

0이 들어올 때까지 무한 반복

병에 들어있는 약의 갯수는 30개가 넘지 않음

 

시작은 무조건 W로 스타트 된다.(완제품이 있어야 반조각도 확인이 되니까)

무조건 W의 갯수는 H보다 적을 수밖에 없음.

 

갯수가 늘어남에 따라 계산이 계속 바뀌기 때문에 1개 ~ 30개 까지 숫자 늘려서 계산하는 것이 best일 것으로 보인다.

 

H 0으로 고정했을 때 문자열 표기

1개일 때 

W H

1 0   W 1개

 

2개일 때

W H

2 0   WW 1개

 

3개일 때 

W H

3 0    WWW 1개

 

N개일 때

W H

 N 0  WWWW.....WWWWW 1개

 

H 1로 고정했을 때 문자열 표기

W H 

1 1 WH  1개

2 1 WWH WHW 2개

3 1 WWWH WWHW WHWW 3개

N 1 N개

 

W가 3개이고 H가 1인 경우 나타낼 수 있는 문자열은 앞에 3개 나온거 맨뒤에 W랑 H 표기한 거 경우의 수이다.

 

결국 

 

W와 H로 표현할 수 있는 길이가 4인 문자열 = W와 H로 표현할 수 있는 길이가 3인 문자열 W or H

 

W 와 H 가 3일 때 내용을 통합해서 계산

 

W H

3 0  WWW 1

2 1 WWH WHW 2

1 2 WHH 1

0 3 불가능

 

이유: W>= H가 될 수 밖에 없음. (무조건 W가 있어야 H가 생성이 가능하기 때문에)

 

dp[3][1] = (dp[3][0] + H) + (dp[2][1] + W)

 

점화식

dp[w][h] =  dp[w][h-1] + dp[w-1][h]   <- 위 식을 풀이

 

 

코드

package test4811;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;


public class Main {

	static long[][] dp;
	static int N;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);
		
		dp = new long[31][31];
		
		algorithm();
		
		while(true) {
			N = sc.nextInt();
			
			if(N == 0) {
				break;
			}
			
			sc.write(dp[N][N]+"\n");
		}
		
		
		sc.close();
	}
	
	static void algorithm() {
		for(int h = 0; h < 31; h++) {
			for(int w = 0; w < 31; w++) {
				if(h > w) {
					continue;
				}
				
				if(h == 0) {
					dp[w][h] = 1;
				}
				else {
					dp[w][h] = dp[w][h-1] + dp[w-1][h];
				}
			}
		}
	}
	
	
	
	static class MyScanner {
		final BufferedWriter writer;
		final BufferedReader reader;
		StringTokenizer tokenizer = null;
		
		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}
		
		String nextToken() throws IOException {
			if(tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}
		
		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}
		
		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}
		
		void write(String text) throws IOException {
			writer.write(text);
		}
		
		void close() throws IOException {
			writer.close();
			reader.close();
		}
	}

}