수열 추측하기

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

 

 

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하 시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

▣ 입력설명

첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의 미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

 

▣ 출력설명

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재 하지 않는 경우는 입력으로 주어지지 않는다.

 

▣ 입력예제 1

4 16

 

▣ 출력예제 1

3 1 2 4

 

 

 

문제 분석

순열 구하기 응용문제입니다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder(); // 출력
	static int N, F, sum =0;
	static int[] b, p, ch;
	int[][] dy = new int[35][35];
	boolean signal = false;
	
	public int combi(int n, int r) {
		if(dy[n][r] > 0) return dy[n][r];
		if(n == r | r == 0) return 1; 
		else return dy[n][r] = combi(n-1,r-1) + combi(n-1,r);
		}
	
	public void DFS(int L, int sum) {
		if(signal) return;
		if(L == N) {
			if(sum == F) {
				for(int x : p) sb.append(x + " ");
				signal = true;
				sb.append('\n');
			}
		}
		else {
			for(int i=1; i<=N; i++) {
				if(ch[i] == 0) {
					ch[i] = 1;
					p[L] = i;
					DFS(L+1, sum + (p[L] * b[L]));
					ch[i] = 0;
				}
			}		
		}
	}
	
	public static void main(String[] args) throws IOException { 
		Main T = new Main();
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		F = Integer.parseInt(st.nextToken());
        
		b = new int[N];
		// b배열 조합으로 초기화
		for(int i=0; i<N; i++) { 
			b[i] = T.combi(N-1, i);
		}
		p = new int[N];
		ch = new int[N+1];
		T.DFS(0, 0);
		System.out.print(sb);
	}
}

 

오늘은 입출력을 Scanner와 System.out.println으로 하나씩 찍는 것이 아니라

BufferedReader, StringTokenizer 그리고 StringBuilder를 이용해보았습니다. 

이론만 학습한 상태라 막상 코드로 쳤을 때 어색함이 있었는데요, 앞으로는 백준을 풀 때도 간간히 적어서 이전 입출력과 메모리, 속도 차이가 어느 정도 나는지 비교하는 포스팅도 올리면 좋을 것 같다는 생각을 했습니다.

 

 

문제 안에서 조합을 가지고 풀 경우, 조합 메서드 구현 코드를 모르고 있었다면 당황했을 문제입니다.

이번 기회에 익히시는 것을 추천하고 시리즈인 순열, 조합, 중복순열, 중복 조합도 같이 한 번에 공부하시면 좋을 것 같습니다.

 

---

 

 

완전 탐색 문제를 풀 때 순열과 조합 코드 구현뿐만 아니라 수학 공식도 종종 쓰이는 것을 알 수 있습니다.

이번 시간에는 각각의 수학 공식과 코드 구현을 해보고, 선 이해 후 암기하시면 좋을 것 같습니다. 

 

순열 구현 코드

import java.util.Scanner;

public class Main {
	static int n,r;
	static int[] arr, pm, ch;
	public void DFS(int L) {
		if(L == r) {
			for(int x : pm) System.out.print(x + " ");
			System.out.println();
		}else {
			for(int i=0; i<n; i++) {
				// 체크배열 0인것만 뻗어나감
				if(ch[i] == 0) {
					// 사용했으므로 체크배열 1로 하고, 백트래킹때 0으로 복귀
					ch[i] = 1;
					pm[L] = arr[i];
					DFS(L+1);
					ch[i] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		r = kb.nextInt();
		ch = new int[n];
		pm = new int[r];
		arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = kb.nextInt();
		}
		T.DFS(0); 
	}

}

 

조합 코드 구현

import java.util.Scanner;

public class Main {
	static int[] combi;
	static int n, r;
	public void DFS(int L, int s) { // L :레벨, s : (기준점이 되는)스타트 번호
		if(L == r) {
			for(int x : combi) System.out.print(x + " ");
			System.out.println();
		}else {
			for(int i=s; i<=n; i++) { // s부터 시작
				combi[L] = i;
				DFS(L+1, i+1);	
			}
		}
	}

	public static void main(String[] args) { 
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		r = kb.nextInt();
		combi = new int[r];
		T.DFS(0,1);
	}

}