[BOJ][Python]N과 M
https://www.acmicpc.net/problem/15649
https://www.acmicpc.net/problem/15650
https://www.acmicpc.net/problem/15651
https://www.acmicpc.net/problem/15652
📌풀이(1)
내가 쓴 풀이(성공)
- backtracking 활용
tmp
: 순열의 각 경우의 수를 구현하기 위한 리스트
def backtracking(n, m, tmp = []):
if len(tmp) == m: # 원하는 갯수만큼 값이 있는 경우
print(*tmp) # 출력
return
for num in range(1, n+1):
if num in tmp: # 이미 들어있는 숫자인 경우, continue
continue
tmp.append(num) # 값 추가
backtracking(n, m, tmp) # 다음 단계 진행
tmp.pop() # 값 꺼냄
n, m = map(int, input().split())
backtracking(n, m)
📌풀이(2)
내가 쓴 풀이(성공)
- (1)이 순열이었다면, (2)는 조합
- 같은 경우가 나타나지 않게 하기 위해, 시작 숫자를 설정
def backtracking(i, n, m, tmp = []):
if len(tmp) == m: # 원하는 갯수만큼 값이 있는 경우
print(*tmp) # 출력
return
for num in range(i, n+1): # 시작 숫자 i 기준
if num in tmp: # 이미 들어있는 숫자인 경우, continue
continue
tmp.append(num)
backtracking(num+1, n, m, tmp) # 다음 숫자로 진행
tmp.pop()
n, m = map(int, input().split())
backtracking(1, n, m)
📌풀이(3)
내가 쓴 풀이(성공)
- 숫자가 중복되는 경우도 고려
def backtracking(n, m, tmp = []):
if len(tmp) == m: # 원하는 갯수만큼 값이 있는 경우
print(*tmp) # 출력
return
for num in range(1, n+1):
tmp.append(num)
backtracking(n, m, tmp)
tmp.pop()
n, m = map(int, input().split())
backtracking(n, m)
📌풀이(4)
내가 쓴 풀이(성공)
- 숫자가 중복되는 경우 고려
- 오름차순의 경우만 고려
def backtracking(i, n, m, tmp = []):
if len(tmp) == m: # 원하는 갯수만큼 값이 있는 경우
print(*tmp) # 출력
return
for num in range(i, n+1):
tmp.append(num)
backtracking(num, n, m, tmp)
tmp.pop()
n, m = map(int, input().split())
backtracking(1, n, m)
📌후기
백트래킹,,,아직 너무 어렵다ㅠㅠㅠ많은 연습이 필요한 것 같다! 같은 유형인데 조금씩 설정을 바꾼 문제들이라 (1)을 해결한 이후에는 빠르게 해결할 수 있었다.
Author And Source
이 문제에 관하여([BOJ][Python]N과 M), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mein-figur/BOJPythonN과-M1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)