[백준 / BOJ] 15651번 N과 M (3) (C++, Python)

링크 : https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

---

문제

---

문제 풀이

앞선 문제들(N과 M (1), N과 M (2))와 같은 맥락을 공유하는 문제다.

 

이번 문제는 같은 수를 여러 번 골라도 된다는 조건이 붙어있다. 그래서 굳이 visited를 사용할 필요 없이, 그냥 dfs를 통해서만 해결하면 된다. (자세한 풀이는 N과 M (1) 문제를 참고해주세요.)

 

for (int i = 1; i <= N; i++) {
    v[val] = i;
    dfs(v, N, M, val + 1);
}

C++ 코드다. 해당 for문에서, 중복이 허용되므로 vector에 i를 저장한 후 dfs를 호출할 시 val 값을 한번 더 증가시켜준 값으로 넣어준다면 자연스레 v[val] = i에 순서대로 값이 넣어진다.

 

for i in range(1, N + 1):
    res.append(i)
    dfs(res, N, M, val + 1)
    res.pop()

파이썬 코드다. 마찬가지로 val 인자만 +1 해주므로 중복을 허용하면서 뽑게 된다.

 

 

C++ 코드 전문

	#include <algorithm>
	#include <iostream>
	#include <vector>
	void dfs(std::vector<int> &v, int N, int M, int val) {
	if (val == M + 1) {
	for (int i = 1; i <= M; ++i)
	std::cout << v[i] << " ";
	std::cout << "\n";
	return;
	}
	for (int i = 1; i <= N; i++) {
	v[val] = i;
	dfs(v, N, M, val + 1);
	}
	}
	void init() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	}
	int main() {
	init();
	int N, M;
	std::cin >> N >> M;
	std::vector<int> v(M + 1);
	dfs(v, N, M, 1);
	return 0;
	}

view raw 15651_N과 M (3) (22.07.27 성공).cpp hosted with ❤ by GitHub

 

Python 코드 전문

	import sys
	input = sys.stdin.readline
	def dfs(res, N, M, val):
	if M + 1 == val:
	print(' '.join(map(str, res)))
	return
	for i in range(1, N + 1):
	res.append(i)
	dfs(res, N, M, val + 1)
	res.pop()
	N, M = map(int, input().split())
	res = []
	dfs(res, N, M, 1)

view raw 15651_N과 M (3) (22.07.27 성공).py hosted with ❤ by GitHub

 

소감