[백준 15649] N과 M(1) [C++]

 

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

15649번: N과 M (1)

 

 

 요즘 다른 분과 하고 있는 리액트 토이 프로젝트 때문에 너무 정신이 없는 나머지... 여기는 정말 신경도 못 썼네요. 리액트도 지금 뭐가 문제인지 막혀서 다른 일에 한 눈 좀 팔 겸 다시 글을 써보려 합니다. 그렇다고 새로운 문제를 풀 정신력은 없어서 결국 옛날에 풀었던 거라도 올려보려 합니다.

 

 이번에도 역시 비슷한 방식이에요. 그래도 지금까지는 DP(다이나믹 프로그래밍) 방식을 사용했는데, 이번에는 재귀입니다. 재귀 중에서도 프로그래밍이나 코딩 테스트에 자주 출제되는 방식이라고 알고 있어요. 그래서 많은 분들께서 연습하고 계시는 것으로 알고 있습니다.

 

재귀 문제 설명: https://minjh1126.tistory.com/m/7

[백준 1003] 피보나치 함수 [C++]

 

1. 문제

 

 N과 M 시리즈의 첫 번째 문제입니다. 일단 N과 M 시리즈는 수열을 만드는 문제인데, 각각의 조건이 있습니다. 주로 중복이 가능한가, 중복된 수가 들어오느냐, 수가 정해져 있느냐 등의 차이입니다. 기본적으로 문제의 흐름은 비슷하니 처음부터 그 형식만 잡고 푸시면 쉽게 푸실 수 있습니다. 

 

 우선 N과 M의 모든 문제의 공통점이 있다면 N과 M입니다. 이번 문제를 보시면

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 이렇게 되어있습니다. 고를 수 있는 수는 1부터 N이고, 중복 없이 한 줄에 M 개를 출력해야 한다는 것이죠. 이 흐름은 똑같으니 기억해두시면 좋습니다. N까지 숫자 M개 고르기!

 

2. 해설

 

 우선 N을 3, M을 2라고 가정해봅시다. 그리고 경우의 수를 적어 봅시다. 

N=3, M=2 경우의 수

 3까지의 숫자 2개씩 적어보면 차례대로 (1,2), (1,3) (2,3)이 나옵니다. 그 외에는 없겠죠? 그러면 우리는 어떻게 이걸 했을까요? 대충 과정을 적어보면

 

1. 남은 수 중 가장 작은 수 고르기

2. 그것보다 더 큰 수 중 아직 안 나간 거 고르기

3. 갯수 맞으면 출력

 

 그렇죠? 그렇습니다. 이걸 과정에서 그림으로 표현해 보자면

1 골랐을 때

2 골랐을 때

 

 이렇게 보면 이해가 가시는지 모르겠습니다. 어찌 됐든 이런 식으로 흘러갑니다. 그래서 이걸 코드로 구현하면 됩니다. 하지만 어떻게요? 

 

 단도직입적으로 얘기하면 재귀하면 됩니다. 1~N까지 과정을 계속 반복하면 됩니다. 제가 사용했던 재귀함수 순서를 적어보자면

 

 1. M의 개수를 채웠는가? - 채웠으면 출력 후 return 해서 돌아감, 안 했으면 진행

 2. for문으로 보다 큰 수들 확인 - 그 수를 거쳤는가? - 거치지 않았으면 그 수를 배열에 넣음, 거쳤으면 패스

 3. 더 이상 없음 - 재귀 끝

 

일단 이렇게 적어봤는데... 코드로 보시는 게 좋을 것 같습니다.

 

 

3. 풀이

 

#include <cstdio>
#include <iostream>
using namespace std;

int m, n;	// N과 M
int arr[9] = {0, };	// 답을 넣을 배열
bool visited[9] = {0, };	// 거쳤는지 확인할 배열

// cnt: 현재 배열에 몇 개가 들어갔는가
void loop(int cnt){
	if(cnt == m){	// 만약 배열의 수가 m과 같으면 출력
		for(int i = 0; i < m; i++){
			cout << arr[i] << ' ';	// 정답이 든 배열 출력
		}
		cout << '\n';
		return;
	}	
	for(int i = 1; i <= n; i++){	// 아직 같지 않다면 반복(1~N까지)
		if(visited[i] != true){	// 이미 거친 수인가? 아니라면 계속
			arr[cnt] = i;	// 현재 값을 배열에 넣음
			visited[i] = true;	// 이번에 거쳤으니 거쳤다는 걸 알려줌
			loop(cnt + 1);	// 재귀, 수가 하나 들어갔으니 cnt + 1
			visited[i] = false;	// 그 수가 이미 들어갔으니 다시 거치지 않음
		}
	}
}

int main(void){
	cin >> n >> m;	// 입력
	loop(0);	// 함수 호출, 아직 배열에 들어간 게 없으므로 0
}

 

 어렵네요 적는 것만으로도... 그런데 저만 그렇게 느낀 건지는 몰라도 처음 봤을 때 for문 하나로 다 되는 건가? 싶지 않나요? 이 for문이 처음에는 이해가 안 갔는데, 한 번 정리해 보도록 하겠습니다. 

재귀 과정

 적어봤지만 여전히 어려워 보이네요. 아마 코드 참고하시면서 푸시다 보면 점차 이해하실 수 있으리라 생각합니다. 혹시나 보시는 분들 중에 이건 뭐죠? 싶으신 분이 있으시다면 댓글에 적어주세요! 제가 할 수 있는 한 열심히 뭐든 해보겠습니다. 아자아자 화이팅~!