[7490] 0 만들기

출처: www.acmicpc.net/problem/7490

7490번: 0 만들기

 

풀이과정

1. 테스트 케이스마다 재귀 호출을 해보자.

2. 0 만드는 함수는 어떻게 할 것인가?

---

참고 코드

import java.io.*;
import java.util.*;

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            func(0, 1, 1, 1, N, "1");
            System.out.println();
        }
    }

    public static void func(int sum, int op, int next, int prev, int N, String s) {
        if (prev == N) {
            sum += (next * op);
            if (sum == 0)
                System.out.println(s);
            return;
        }

        func(sum, op, next * 10 + prev + 1, prev + 1, N, s + ' ' + (prev + 1));
        func(sum + op * next, 1, prev + 1, prev + 1, N, s + '+' + (prev + 1));
        func(sum + op * next, -1, prev + 1, prev + 1, N, s + '-' + (prev + 1));
    }
}

코드 출처:  www.acmicpc.net/source/22356747

로그인

memo

재귀를 구현할 때엔

함수에 조건문 처리 구조를 떠올리고

그 안에 어떠한 규칙이 들어갈지 문제를 보고 유추해내야한다.

이번 문제는 연산자의 규칙성을 따져서 재귀함수로 구현해야하는 문제였다.

다시 구현해 보아야겠다.