[백준 1149번] N과 M(2) - java

문제 설명

1. 숫자 N, M을 입력받는다.

2. 1부터 N까지의 중복 없는 숫자를 사용하여 M의 길이를 갖는 순열을 만든다.

3. 오름차순으로 출력한다.

풀이 과정

 1. 간단한 백트래킹 문제이다.

 2. 숫자를 하나씩 만들어가다가 M의 길이에 도달하면 출력하면 된다.

 3. 간단하게 1에서 만들수 있는수, 2에서 만들수있는수....이렇게 하면 중복 체크 필요 없이도 구현이 충분이 가능하다. (중복없이 구현하는게 더 효율적일 것 같아서 구현 방법을 바꾸었다.)

ex) (N=4, M=3인 경우)

1, 2, 3, 4 네 가지의 숫자가 있고, 숫자는 오름차순으로 출력하여야 한다.

 

줄	1	1	2
줄	2	2	3
줄	3(출력)	4(출력)	4(출력)

위의 표를 보면, 위에서 아래로 숫자가 만들어 지고, M과 줄이 같아지는 맨 아래에서 출력된다.

또, (1-2-3) (1-2-4) 이 숫자들의 경우는 위에서부터 DFS를 통해 만들면 금방 만들 수 있다.

 

for문 내에서 1로 시작하는 경우 dfs를 돌리며 M과 배열의 위치가 같아지면 출력하고 return하면 쉽게 구할 수 있을 것이다.

 

코드