Prob

Approach

itertools를 사용한다.

음수 // 양수에 주의하여 작성한다.

Code

from itertools import permutations
import sys
def cal_formul(case, num):
    res = num[0]
    for i in range(len(num) - 1):
        if case[i] == '+':
            res += num[i + 1]
        elif case[i] == '-':
            res -= num[i + 1]
        elif case[i] == '*':
            res *= num[i + 1]
        elif case[i] == '/':
            if res < 0:
                res = -(abs(res) // num[i + 1])
            else:
                res //= num[i + 1]
    return res

if __name__ == "__main__":
    N = int(input())
    num = list(map(int, input().split()))
    oper = list(map(int, input().split()))
    m_oper = ""

    for i in range(len(oper)):
        if oper[i] > 0 and i == 0:
            m_oper += "+" * oper[i]
        elif oper[i] > 0 and i == 1:
            m_oper += "-" * oper[i]
        elif oper[i] > 0 and i == 2:
            m_oper += "*" * oper[i]
        elif oper[i] > 0 and i == 3:
            m_oper += "/" * oper[i]
    m_oper = list(set((permutations(m_oper, len(m_oper)))))
    min = sys.maxsize
    max = -sys.maxsize - 1
    
    for case in m_oper:
        val = cal_formul(case, num)
        if val < min : min = val
        if val > max : max = val

    print(max)
    print(min)

출처

https://www.acmicpc.net/problem/14888

Prob

Approach

PyPy를 사용하여 제출한다.

미입력된 부분만 뽑아서 후보 숫자를 구해 백트래킹한다.

Code

import sys
m_board = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(9)]
prob = [(i, j) for i in range(9) for j in range(9) if m_board[i][j] == 0]

def candi_num(i, j):
    num = [k for k in range(1, 10)]
    
    for m in range(9):
        if m_board[i][m] in num:
            num.remove(m_board[i][m])
        if m_board[m][j] in num:
            num.remove(m_board[m][j])
    i = i // 3
    j = j // 3

    for p in range(i * 3, (i + 1) * 3):
        for q in range(j * 3, (j + 1) * 3):
            if m_board[p][q] in num:
                num.remove(m_board[p][q])
    return num

flag = False
def dfs(x):
    global flag
    
    if flag:
        return

    if x == len(prob):
        for k in range(len(m_board)):
            sys.stdout.write(' '.join(map(str, m_board[k])) + '\n')
        flag = True
        return
    else:
        (i, j) = prob[x]
        can_num = candi_num(i, j)
        for num in can_num:
            m_board[i][j] = num
            dfs(x + 1)
            m_board[i][j] = 0
dfs(0)

출처

https://www.acmicpc.net/problem/2580

Prob

Approach

시간 초과가 나와서 다른 글들을 본 결과.. Python 으론 고난이도 문제라고 한다...

다른 방법들을 찾았지만 딱히.. 해결하지 못했다..

아이러니한건 pypy3 에서는 제출 가능..

모든 경우를 찾아야 하므로 브루트 포스다.

Code

def m_check(x):
    for j in range(x):
        if m_row[x] == m_row[j] or abs(m_row[x] - m_row[j]) == x - j:
            return False
    return True

def dfs(x):
    global res

    if x == N :
        res += 1
    else:
        for i in range(N):
            m_row[x] = i
            if m_check(x):
                dfs(x + 1)

if __name__ == "__main__" :
    N = int(input())
    m_row = [0] * N
    res = 0
    dfs(0)
    print(res)

출처

https://www.acmicpc.net/problem/9663