[백준/JAVA] 7490번: 0 만들기

📖 문제

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

 

 

 

💡  풀이 방식

• 브루트포스 + 백트래킹 + 문자열

 

[DFS 함수]

- 인자: now - 현재 탐색 중인 숫자의 위치 (1부터 시작) / num - 현재 숫자 / sign - 현재 숫자의 부호 (1이면 +, -1이면 -) / sum - 현재까지의 합계 / str - 현재까지의 연산식

- 종료 조건: 수열의 맨 마지막 숫자 N에 도달했을 경우

- 부호가 [공백이냐/+냐/-냐] 에 따라 재귀함수를 호출한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int T, N;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        
        while(T --> 0) {
            N = Integer.parseInt(br.readLine());
           dfs(1, 1, 1, 0, "1");
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
  
    private static void dfs(int now, int num, int sign, int sum, String str) {
        if(now == N) {
            sum = sum + (num*sign);
            
            if(sum == 0)
                sb.append(str).append("\n");
            return;
        }
        
       dfs(now+1, num*10 + (now+1), sign, sum,              str + " " + String.valueOf(now+1));
       dfs(now+1, now+1,            1,    sum + (num*sign), str + "+" + String.valueOf(now+1));
       dfs(now+1, now+1,           -1,    sum + (num*sign), str + "-" + String.valueOf(now+1));
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

저 풀이가 가장 짧아서 저걸로 제출하긴 했는데, 함수 인자가 너무 많은 것 같당,,ㅠ

 

- 이건 한 문자열에서 숫자와 부호를 스트림 API 를 활용해서 분리하셨다.

[BOJ] 백준 7490번 0 만들기 (Java)

---

💦 어려웠던 점

- 재귀인 건 캐치했고, 재귀 함수는 잘 작성한 것 같은데 한 줄의 문자열에서 숫자와 부호를 분리해서 계산을 어떻게 할지를 해결하려고 하는 시간이 오래 걸렸다..

 

 

🧐 새로 알게 된 내용

한 문자열 내에서 숫자와 부호를 분리해 계산하는 방법 (재귀)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BaekJoon] 7490 0 만들기 (java)