[BOJ_23842] 성냥개비

백준 23842번 성냥개비

https://www.acmicpc.net/problem/23842

23842번: 성냥개비

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

	static String ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine())-4;
		
		int[] map = {6,2,5,5,4,5,6,3,7,6};
		ans = "impossible";
		perm(0, new int[6], map, N);
		System.out.println(ans);
	}

	private static void perm(int cnt, int[] num, int[] map, int N) {
		
		if(cnt==6) {
			int total = 0;
			for (int i = 0; i < 6; i++) {
				total += map[num[i]];
			}
			if(total!=N) return;
			int a = num[0]*10 + num[1];
			int b = num[2]*10 + num[3];
			int c = num[4]*10 + num[5];
			StringBuilder answer = new StringBuilder();
			if(a+b==c) {
				answer.append(num[0]);
				answer.append(num[1]);
				answer.append("+");
				answer.append(num[2]);
				answer.append(num[3]);
				answer.append("=");
				answer.append(num[4]);
				answer.append(num[5]);
				ans = answer.toString();
                System.out.println(ans);
				System.exit(0);
			}
 			return;
		}
		
		for (int i = 0; i <= 9; i++) {
			num[cnt] = i;
			perm(cnt+1, num, map, N);
		}
	}

}

잘 푼 점 :

1. character를 조합해서 출력해야하는 경우 + 로 이어가며 String을 만들지 않고 StringBuilder를 사용하였다. StringBuilder를 사용하면 그냥 String을 이어 붙이는 것보다 시간이 절약된다.

2. 답이 될 수 있는 걸 처음 찾자마자 System.exit(0)으로 프로그램을 강제 종료 시켜주었다. 다른 답을 찾지 않고 종료하므로 시간이 3분의 1가량 줄었다!

 

아쉬운 점 :

for (int i = 0; i <= 9; i++) {
	num[cnt] = i;
	perm(cnt+1, num, map, N);
}

이 부분에서 전체 N이 얼마나 남았는지 확인할 수 있었을 것이다. 즉, perm이 재귀로 불릴 때마다 num배열에 넣는 숫자에 필요한 성냥개비 개수를 바로바로 N에서 빼줄 수 있다. 이러면 나중에 또 for문을 돌려서 성냥개비 개수를 더해줄 필요가 없다.