https://www.acmicpc.net/problem/15651
문제
> 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
> 1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.접근
재귀를 사용하여 배열 num에 1부터 N까지 M개의 원소를 가지는 수열을 만든다.
재귀로 넘길 때, 즉 새로운 자리에 어떤수가 올 수 있는지를 정할 때, 중복이 가능하다고 했으므로 1부터 올 수 있다.
따라서 반복문을 매 자리마다 1부터 N까지 해주며 탈출 조건으론 현재 저장하려는 인덱스의 번호가 M이랑 같아지면 끝낸다.
문제해결
> N과 M을 선언하고 수열을 담을 배열 num을 선언한다.
> N과 M을 입력받고 배열의 크기를 M으로 초기화 해준다.
> 수열을 만드는 NtoM 메소드에 인자로 rst값 즉, 배열의 원소수 또는 인덱스 번호를 0으로 주고 호출한다.
> 메소드 내부에서 rst값에 대해 M과 같으면 조건을 만족하므로 배열에 저장된 수열을 출력한다.
> 아니면 for문으로 1부터 N까지 매 자리마다 반복하며 재귀로 rst에 1을 추가해 주며 새로운 자릿수를 탐색한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//15651번 N과 M (3)
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] num;
static void NtoM(int rst) {
if(rst >= M) {
for(int i : num) sb.append(i).append(' ');
sb.append('\n');
return;
}
for(int i = 1; i <= N; i++) {
num[rst] = i;
NtoM(rst+1);
}
}
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());
M = Integer.parseInt(st.nextToken());
num = new int[M];
NtoM(0);
System.out.print(sb);
}
}
후기
계속 컴파일 에러가 나서 도대체 뭐가 문제인지 몰랐는데
백준에서 java는 제출할 때 class의 명이 Main이 아니면 안된다고 한다. 두번째 소스 파일이라 Main2로 해서 그랬다.. 참
