[백준] 골드5 7490번 0 만들기

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

 

시간 제한: 1초

메모리 제한:  128MB

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

7490번: 0 만들기

---

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

 

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

 

예제 입출력

예제 번호	입력	출력
1	2 3 7	1+2-3 1+2-3+4-5-6+7 1+2-3-4+5+6-7 1-2 3+4+5+6+7 1-2 3-4 5+6 7 1-2+3+4-5+6-7 1-2-3-4-5+6+7

---

Ⅰ문제 분석하기

(본 문제 분석은 예제 입출력 1번은 기준으로 작성되었습니다.

 

TEST CASE 1-1

+혹은 -기호가 결정 시 이전 계산을 진행

EX) 1+2 < 계산진행하지 않음 

       사유: 1+23이 될 수 있기 때문

       1-2+  < 1-2의 연산을 진행

따라서 순서는 아래와 같이 진행된다.

① + 혹은 - 가 오면 해당 기호 앞의 연산을 수행, SUM값에 넣음

    SUM: 현재 정해진 기호 앞의 연산이 종료된 값. SUM+(index*op)

    OP: 이번에 정해진 기호(+면 1, -면 -1)

   NUM: INDEX+1 

   INDEX: INDEX+1

② 공백이 오면 아무연산을 수행하지 않음

    SUM: 이전 값과 동일

    OP: 이전 값과 동일

    NUM: (NUM*10)+(INDEX+1)

   INDEX: INDEX+1

 

---

 

Ⅱ 슈도코드 작성하기

/*
* 작성자, 1.0, 2024.03.18 누Ring <dierdia@naver.com>
*
* BAEKJOON 골드5 7490 0 만들기
* 문제 링크: https://www.acmicpc.net/problem/7490
* 작성 언어: Pseudo-code
*/

[글로벌 변수 선언] N
[글로벌 StringBuilder 선언] sb
-------------------------------
MAIN문 
{
    [입출력 버퍼드리더 선언]
    [변수 선언] TC = 입력 정수 값

    for(TC입력값 만큼 반복)
    {
        [변수 선언] N = 입력 정수 값
        [StringBuilder 초기화] sb
        [함수 실행] DFS(int 인덱스, int 합, String 계산식, int 부호, int 현재 숫자)
                   초기값은 1, 0, "1", 1(앞에 0+가 있는것으로 넣어준다, 따라서 +부호로 시작),1
                   부호를 1, -1로 넣어줌으로서 곱하기 연산으로 계산가능하게 한다.
                   인덱스는 현재 바라보는 숫자(의 순서)임으로
                   어떠한 연산시에도 무조건 INDEX+1로 넘겨줘야한다.
    }
}
-------------------------------
DFS 함수 (int 인덱스, int 합, String 계산식, int 부호, int 현재 숫자)
{
	//dfs함수 종료 조건을 우선 작성하여 무한반복이 되지않도록 함
	IF(인덱스가 끝까지 갔을 때=N일때)
    {
    	합=합+(현재숫자*이전 부호)
        IF(합 = 0이면)
        {
        	정답임으로 StringBuilder에 추가
            (혹은 바로 출력)
        }
        return
    }
    
    //① 공백을 넣게 될 경우
    DFS(INDEX+1, SUM, 계산식, 부호, 현재숫자*10+다음숫자 )
    [설명] INDEX는 언제나 +1해준다
          아직 부호가 확정되지않아 (1일지 12일지 123이 될지 모름으로) 연산 없음=SUM은 변동 없음
          현재까지의 계산식에 공란을 넣고 다음 인덱스 숫자를 넣어준다.
          부호가 확정되지 않았기 때문에 변동 없음
          현재 숫자를 *10한 후 다음 숫자를 더해준다
          EX) 1 2 였는데 공란이 추가될 경우 1 2 3이 된다.
              기존 합 12 -> 120 + 3 = 123
          
    //② 덧샘 기호를 넣게 될 경우
    DFS(INDEX+1, 지금까지의 합+(현재 숫자*1), 계산식=(문자열+다음숫자) ,1 , 다음 숫자);
    [설명] INDEX는 언제나 +1
          기호가 확정이 났기 떄문에 계산을 진행. 
          EX) 1 + 2 + 3 일 경우 1+2를 연산
              사유: 3의 경우 34가 될 수도 있기 때문
    
    //③ 뺄샘 기호를 넣게 될 경우
    DFS(INDEX+1, SUM+(num*op), (계산식+"-"+Integer.toString(index+1)),-1,다음 숫자);
    [설명]마이너스 연산의 경우 OP를 -1로 설정하여 뺄샘 연산이 되도록 한다.
}

 

---

Ⅲ 코드 구현 ( 구현 언어: JAVA )

/*
* 작성자, 1.0, 202Y.MM.YY 누Ring <dierdia@naver.com>
*
* BAEKJOON 골드5 7490 0 만들기
* 문제 링크: https://www.acmicpc.net/problem/7490
* 작성 언어: JAVA
*/
import java.util.*;
import java.io.*;

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

public class Main {
	public static StringBuilder sb;
	public static int N;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int TC=Integer.parseInt(br.readLine());
		for(int tc=0;tc<TC;tc++)
		{
			N=Integer.parseInt(br.readLine());
			//dfs 로직
			//index(n-1회의 기호를 넣으면서 반복, 현재의 계산값, 현재의 계산식, 이전계산기호, 현재 숫자)
			sb=new StringBuilder();
			dfs(1,0,"1",1,1); 
			
			System.out.println(sb);
		}

	}
	public static void dfs(int index, int sum, String his,int op, int num)
	{
		if(index==N)//n-1번의 기호를 모두 넣었다면
		{
			sum+=(num*op);
			if(sum==0) //합산이 0이 되었다면 출력리스트에 추가
			{
				sb.append(his+"\n");
			}
			return;
		}
		
		//공백 넣기
		dfs(index+1,sum,his+" "+Integer.toString(index+1),op,(num*10+(index+1)));
		
		//기호결정+숫자확정+계산
		//덧셈 기호 넣기
		dfs(index+1, sum+(num*op), his+"+"+Integer.toString(index+1),1,index+1);
		//뺄셈 기호 넣기
		dfs(index+1, sum+(num*op), his+"-"+Integer.toString(index+1),-1,index+1);
	}
}