[Algorithm🧬] 정올 1169 : 주사위 던지기 1

문제

import sys

def DFS(n, m, level):
    if level == n:
        for i in range(n):
            print(order[i], end=' ')
        print()
        return

    if m == 1:
        for j in range(1, 7):
            order[level] = j
            DFS(n, m, level + 1)
    elif m == 2:
        for j in range(1, 7):
            if level == 0:
                order[level] = j
                DFS(n, m, level + 1)
            # 겹치는게 나오면 안되니까 이전 것보다 크거나 같을 때만 넣어야 함. 1 1 2 -> 2 1 1 이렇게 되지 않고 2 2 2 부터 시작하게
            elif level > 0 and order[level - 1] <= j:
                order[level] = j
                DFS(n, m, level + 1)
    elif m == 3:
        for j in range(1, 7):
            # 다 달라야 하니까 앞에 없는 것만 가능
            if not (j in order[:level]):
                order[level] = j
                DFS(n, m, level + 1)





n, m = map(int, sys.stdin.readline().split())
order = [0] * n

DFS(n, m, 0)

DFS 오랜만에 풀었더니 order 배열 따로 두고 마지막에 출력하는게 기억이 안나서 헤맸다.

2트

위에랑 똑같이 풀었는데, If 로 조건문 구분해주는 것 말고 더 좋은 방법이 있을 것 같아서 찾아본 코드.

2 같이 전의 것 보다 커야하는 경우는 인자를 하나 더 줘서 돌리고
3 같이 전부 달라야 하는 경우는 ch 배열을 이용하면 좀 더 재귀에 알맞는 코드가 되는 것 같다.

import sys
from collections import deque

readl = sys.stdin.readline

def DFS(level):
	if level == n:
		print(*res, sep=' ')
		return

	for i in range(1, 7):
		res[level] = i
		DFS(level + 1)

def DFS2(level, start):
	if level == n:
		print(*res, sep=' ')
		return

	for i in range(start, 7):
		res[level] = i
		DFS2(level + 1, i)

def DFS3(level):
	if level == n:
		print(*res, sep=' ')
		return

	for i in range(1, 7):
		if ch[i] == 1:
			continue
		ch[i] = 1
		res[level] = i
		DFS3(level + 1)
		ch[i] = 0

n, m = map(int, readl().split())
ch = [0] * 7
res = [0] * n

if m == 1:
	DFS(0)
elif m == 2:
	DFS2(0, 1)
elif m == 3:
	DFS3(0)