백준 python 2580번 스도쿠 / 14888번 /

백준 python 2580번 스도쿠

 

 

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

 

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

제한

baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.

C++14: 80ms

Java: 292ms

PyPy3: 1172ms

 

Python

def AbleNumber(n, m):
    ableNumber = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for i in range(9):
        if graph[n][i] in ableNumber:
            ableNumber.remove(graph[n][i])

    for i in range(9):
        if graph[i][m] in ableNumber:
            ableNumber.remove(graph[i][m])

    sub_n = n // 3
    sub_m = m // 3

    for i in range(sub_n * 3, sub_n * 3 + 3):
        for j in range(sub_m * 3, sub_m * 3 + 3):
            if graph[i][j] in ableNumber:
                ableNumber.remove(graph[i][j])
    return ableNumber

graph = [list(map(int, input().split())) for _ in range(9)]

def BackT(idx):
    if idx == 81:
        return True

    for i in range(idx, 81):
        sub_n = i // 9
        sub_m = i % 9

        if graph[sub_n][sub_m] != 0:
            if i == 80:
                return True
            continue

        ableNumber = AbleNumber(sub_n, sub_m)
        for j in ableNumber:
            graph[sub_n][sub_m] = j
            if BackT(i + 1):
                return True
            graph[sub_n][sub_m] = 0
        return False
        

BackT(0)
for i in range(9):
    for j in range(9):
        print(graph[i][j], end=' ')
    print()

 

백준 pyton 14888번

 

 

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

Python

n = int(input())
number = list(map(int, input().split()))
operator = list(map(int, input().split()))
result_max = -1e9
result_min = 1e9

def BackTrack(index, start):
    global result_max, result_min
    if index == n - 1:
        result_max = max(start, result_max)
        result_min = min(start, result_min)
        return

    for i in range(4):
        if operator[i % 4] == 0:
            continue
        operator[i % 4] -= 1
        BackTrack(index + 1, Operator(start, number[index + 1], i % 4))
        operator[i % 4] += 1


def Operator(x, y, oper):
    if oper == 0:
        return x + y
    elif oper == 1:
        return x - y
    elif oper == 2:
        return x * y
    else:
        if x < 0:
            result = (-x) // y
            return -result
        else:
            return x // y

BackTrack(0, number[0])
print(result_max)
print(result_min)

반응형

백준 python 6603번

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

 

입력의 마지막 줄에는 0이 하나 주어진다. 

 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

 

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

 

 

Python

i = 1
while True:
    globals()['lotto{}'.format(i)] = list(map(int, input().split()))
    if globals()['lotto{}'.format(i)][0] == 0:
        break
    globals()['visited{}'.format(i)] = [False] * (globals()['lotto{}'.format(i)][0] + 1)
    i += 1
result = list()


def BackTracking(depth, start, lotto, visited):
    global string
    if depth == 6:
        print(' '.join(map(str, result)))
        return

    for i in range(start, lotto[0]+1):
        if visited[i]:
           continue
        visited[i] = True
        result.append(lotto[i])
        BackTracking(depth+1, i, lotto, visited)
        result.pop()
        visited[i] = False


for i in range(1, i):
    BackTracking(0, 1, globals()['lotto{}'.format(i)], globals()['visited{}'.format(i)])
    print()