[Java] 프로그래머스 1831.4단고음 (Lv.4)

https://programmers.co.kr/learn/courses/30/lessons/1831

코딩테스트 연습 - 4단 고음

원래는 이분탐색의 Lv.4 문제를 풀려고 했는데, 저도 구현하다가 애매한 부분이 있어 확인해보니 문제에 오류가 있다는 얘기가 많아서 다른 Lv.4 문제를 가져왔습니다.

 

연산후의 값이 주어지고 그 값이 연산을 통해 만들 수 있는가를 검증하거나 가능한 경우의 수를 찾는 문제는 주어진 값부터 연산을 거꾸로 짚어가며 풀이하면 쉽고 빠르게 풀리는 경우가 많습니다. 이번 문제도 그런 유형이었는데요.

 

처음엔 3단고음이라는 연산이 중첩되어 계산되는 것을 stack처럼 중첩의 갯수를 카운팅해서 풀이하려고 했는데 구현 난이도가 어마어마 했을 뿐만 아니라 통과도 실패했습니다.

QnA의 도움을 얻어, 이 3단고음이라는 연산은 뒤에서부터 읽어들어갈때, +의 갯수가 2개보다 큰 경우 *하나와 묶어서 사라질 수 있다는걸 알았습니다. 즉, 거꾸로 3단고음 연산이 동작할때 1을 뺄때 +의 갯수를 늘려주고 (+를 역산), +의 갯수가 두개이상이면 3으로 나눠지면서 두개와 소멸하고, 초기값인 1에 도달했을때 +와 *가 모두 상쇄되었으면 카운트를 1 늘려주었습니다.

재귀호출 중간에 ++의 갯수만큼 *의 역산이 이루어져야 하는데 불가능한 경우 가지치기 했습니다.

 

해당 아이디어를 바탕으로 dfs를 응용한 재귀문을 작성해 테스트케이스를 통과했습니다.

테스트케이스가 하나뿐이라 예외에 걸릴지는 잘 모르겠네요.

 

public class q1831_Programmers_4단고음 {
	static int answer;

	public static void main(String[] args) {

//		int[] input = { 15, 24, 41 };
		int[] input = { 15, 24, 41, 2147483647 };

		for (int i = 0; i < input.length; i++) {
			System.out.println(solution(input[i]));
		}
	}

	private static int solution(int n) {
		answer = 0;

		dfs(n, 0);

		return answer;
	}

	private static void dfs(int now, int depth) {
		//System.out.println("now:" + now + "   depth:" + depth);
		
		if (now == 1 && depth == 0) {
			answer++;
			return;
		}
		
		if (now < Math.pow(3, (depth / 2))) {
			return;
		}

		dfs(now - 1, depth + 1);
		
		if (depth >= 2 && now >= 3 && now % 3 == 0) {
			dfs(now / 3, depth - 2);
		}

	}

}