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

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

15652번: N과 M (4)

---

문제

---

문제 풀이

앞선 문제들(N과 M (1), N과 M (2), N과 M(3))과 같은 맥락을 공유하는 문제다. 특히 N과 M(3)과 아주 유사하다.

 

C++ 상세 풀이

전 문제와 유사하게 해당 문제는 굳이 visited를 사용할 필요가 없다. 비내림차순으로 출력하면 된다고 했으니, C++의 경우는 간단하게 이전 숫자와의 크기를 비교하도록 조건문을 하나 추가해준다.

 

if (v[val - 1] <= i)

Python 상세 풀이

파이썬의 경우에는 빈 리스트를 선언했고, dfs에 들어왔다 나갈 때마다 append, pop 연산이 이루어지니 위의 조건문을 선언하는 방법은 indexerror이므로 불가능하다. 대신 파이썬은 dfs함수 안에서 for문을 돌 때, i를 인자로 건네줘 i부터 다시 for문을 돌도록 구현했다.

 

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

 

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++) {
	if (v[val - 1] <= 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 15652_N과 M (4) (22.07.31 성공).cpp hosted with ❤ by GitHub

 

Python 코드 전문

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

view raw 15652_N과 M (4) (22.07.31 성공).py hosted with ❤ by GitHub

 

소감