[Algo Rhythm🕺💃] BOJ 17520. Balanced String

📚 문제 설명

0과 1로 이루어진 이진 문자열 0101101은 0과 1의 개수의 차이가 1 이하이다. 뿐만 아니라, 첫 번째 문자를 포함하는 모든 부분 문자열 0, 01, 010, 0101, 01011, 010110, 0101101 모두 0과 1의 개수의 차이가 1 이하이다.

이와 같이, 이진 문자열 중에서 첫 번째 문자를 포함하는 모든 부분 문자열의 0과 1의 개수의 차이가 1이하인 문자열을 균형잡힌 문자열이라 부른다. 문자열 자체도 자신의 부분 문자열이다.

양의 정수 n 이 주어질 때, 길이가 n 인 이진 문자열 중에서 균형잡힌 문자열의 수를 구하는 프로그램을 작성하시오.

예를 들어, n = 3인 경우에는 010, 011, 100, 101 네 개의 문자열이 균형잡힌 문자열이다.

 

입력
입력은 표준입력을 사용한다. 첫 번째 줄에 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다.

출력
출력은 표준출력을 사용한다. 길이가 n 인 이진 문자열 중에서 균형잡힌 문자열의 개수를 16769023로 나눈 나머지 값을 한 줄에 출력한다.

 

🎯 어떻게 풀었나

1. Backtracking (시간 초과)

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

public class Main {
	static int nBalancedString  = 0;
	
	public static void main(String[] args) {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			int n = Integer.parseInt(br.readLine());
			
			backtrack(0, 0, 0, n);
			
			System.out.println(nBalancedString % 16769023);
		} catch (NumberFormatException | IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static void backtrack(int nZero, int nOne, int level, int n) {
		if(level == n) {
			nBalancedString++;
			return;
		}
		
		if(Math.abs((nZero + 1) - nOne) <= 1) {
			backtrack(nZero + 1, nOne, level + 1, n);
		}
		
		if(Math.abs(nZero - (nOne + 1)) <= 1) {
			backtrack(nZero, nOne + 1, level + 1, n);
		}	
	}
}

 

2. 숨겨진 성질 이용

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

public class BOJ_17520 {	
	public static void main(String[] args) {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			int n = Integer.parseInt(br.readLine());
			int ans = 1;
			int power = (n % 2 == 0) ? n / 2 : n / 2 + 1;
			
			for(int i = 0; i < power; i++) {
				ans = (ans * 2) % 16769023;
			}
			
			System.out.println(ans);
		} catch (NumberFormatException | IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

 

🧐 왜 저렇게 풀었나

1. Backtracking

균형잡힌 문자열이란 모든 부분 문자열의 0과 1의 개수의 차이가 1이하인 문자열을 말한다. 이것을 잘 생각해보면 한 문자열에서 0 혹은 1을 붙여서 자식 문자열을 만들 때 해당 문자열이 균형잡힌 문자열이 아니라면 그 자식도 절대 균형잡힌 문자열이 될 수 없다는 것을 알 수 있다.

 

이 성질을 이용하면 이 문제는 길이가 0인 빈 문자열부터 뒤에 0 혹은 1을 붙여가면서 자식 문자열을 만드는데 그 자식이 균형잡힌 문자열일 때만 생성하면서 길이가 n인 문자열들의 개수를 세는 문제로 이해할 수 있다. 다음은 이해를 돕기 위한 그림이다.

 

 

이렇게 문제를 이해하고 나면 이는 전형적인 backtracking 문제라는 것을 알 수 있다.

하지만 시간 초과로 인해 실패했다.

 

2. 숨겨진 성질 이용

첫번째 접근처럼 Tree로 본다면 level이 짝수일 때 자식의 수는 부모의 수 * 2 인 것을 알 수 있다. 그리고 level이 홀수일 때 자식의 수는 부모의 수와 같다는 것을 알 수 있다.
이 성질을 이용해서 코드를 구현하니 통과할 수 있었다.

 

 

📖 무엇을 배웠나

ACM-ICPC 문제는 제한시간을 엄격하게 제안하는 듯한 느낌을 받았다.