[백준] 2231 분해합 - DFS + 완전탐색 JAVA

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

2231번: 분해합

 

문제풀이

일반적인 DFS 문제입니다.

종료조건은 1 ~ N 까지만 조사하도록 설정하면 됩니다.

이외의 것은 일반적인 재귀함수를 사용하여 해결했습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N;
	public static int result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	simulate(1, 0);
    	System.out.println(result);
    }
    
    public static void simulate(int idx, int sum) {
    	if( idx > N) {
    		result = 0;
    		return ;
    	}
    	if( sum == N ) {
    		result = idx - 1;
    		return ;
    	}
    	
    	int idxtemp = idx;
    	int sumtemp = idx;
    	while(idxtemp > 0) {
    		sumtemp += idxtemp % 10;
    		idxtemp /= 10;
    	}
    	
    	simulate(idx+1, sumtemp);
    	
    }
 
}