[백준][파이썬] 15683번 감시

문제 번호 : 15683
문제 출처 : https://www.acmicpc.net/problem/15683

Code

import sys


def watch(watched_set, index):              # index : count, cctv 개수 만큼 탐색
    if index == len(cctvs):
        result.append(len(watched_set))
        return
    else:
        for cctv in cctvs[index]:           # cctv[index] 에는 한 cctv의 경우의 수가 모두 저장
            new_s = set(watched_set)
            view(cctv, new_s)               # 각도에 따라서 cctv로 볼 수 있는 위치를 집합에 저장
            watch(new_s, index + 1)


def view(cc, viewd):
    x, y, cctv_type, angle = cc
    d = []
    for idx in range(4):
        d = direction[cctv_type][(idx + angle) % 4] # cctv type과 angle이 정해졌을 때 방향
        if d == 1:
            nx, ny = x + dx[idx], y + dy[idx]
            while -1 < nx < h and -1 < ny < w and office[nx][ny] != 6:
                if office[nx][ny] == 0:     # cctv 있는 위치는 저장 안하도록
                    viewd.add((nx, ny))
                nx = nx + dx[idx]
                ny = ny + dy[idx]


h, w = map(int, input().split())
office = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]

angles = [4, 2, 4, 4, 1]        # type별로 가능한 각도 수
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
direction = [[0, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1,], [1, 1, 1, 1]] # 각도 별로 shift할 리스트

cctvs = []
answer = 0
result = []

for i in range(h):
    for j in range(w):
        if 0< office[i][j] <6:  # cctvs 에 하나의 cctv에서 가능한 각도를 하나의 리스트에 모두 저장
            cctvs.append([[i, j, office[i][j] - 1, angle] for angle in range(angles[office[i][j] - 1])])
        if office[i][j] == 0:   # 0의 개수 세기기
            answer+= 1
watched = set([])

watch(watched, 0)
answer = answer - max(result)   # 0의 개수에서 cctv로 본 위치의 수 빼서 답 구하기
print(answer)

Idea

1. cctv 종류 별로 가능한 각도 수가 다르다.
2. 처음에는 cctv로 본 곳을 #으로 표시했는데 시간이 많이 걸렸다.
3. 입력받은 이차원 리스트를 수정하지 않고 cctv가 본 위치를 저장하는 집합을 만들었다.
4. cctv가 본 위치가 가장 많은 상황에서 0의 개수에서 집합의 길이를 빼면 사각지대를 구할 수 있다.

[백준][파이썬]

문제 번호 : 16637
문제 출처 : https://www.acmicpc.net/problem/16637

Code

from itertools import combinations


def disable(tu):    # 괄호를 둘 수 있는가 판별
    if len(tu) > 1:
        tmp_li = list(combinations(tu, 2))

        for tmp in tmp_li:  # 2개를 골라와서 그 차이가 1이면 괄호를 둘 수 없다.
            if max(tmp) < min(tmp) + 2:
                return True

        return False

    else:
        return False


def calc(expr):
    result = 0
    old_op_idx = -1
    old_op = '+'
    op1 = 0
    for i in range(len(expr)):
        if expr[i] == '+' or expr[i] == '*' 
                or expr[i] == '-' and i - old_op_idx != 1:
            op1 = result
            op2 = expr[old_op_idx+1:i]
            result = eval(str(result) + old_op + expr[old_op_idx+1:i])
            old_op = expr[i]
            old_op_idx = i
    result = eval(str(result) + old_op + expr[old_op_idx+1:])
    return result


n = int(input())
expression = input()    # 수식 입력
num_op = n//2           # 연산자 개수 = 수식 길이 // 2
answer = - 2**31        # -2**31 < ANSWER < 2**31
maximum = 2**31

if n == 1:      # 길이가 1 ==> 숫자 하나 입력
    print(int(expression))
elif n == 3:    # 길이가 3 ==> 연산자 하나를 가지는 수식 입력
    print(eval(expression))
else:
    for br in range(1, num_op//2+1):    # br : 괄호 갯수, 괄호의 최대 개수는 연산자 수 // 2
        cases = list(combinations(range(num_op), br))   # 괄호 br 개를 넣을 수 있는 경우의 수를 모두 찾아냄
        for case in cases:
            if disable(case):   # 괄호를 넣을 수 있는지 판별
                continue
            else:
                ex = expression # 수식을 잠깐 저장
                for i in range(len(case)-1, -1, -1):                # 수식을 뒤에서 부터 수정
                    i = case[i]                                     # 앞에서부터 수정하면 뒷 부분의 index값이 변함
                    ex_li = list(ex) # 수식의 중간을 수정하기 위해 list 형으로 잠시 변환
                    ex_li[i*2: i*2+3] = str(eval(ex[i*2:i*2+3]))    # 수식의 중간 부분 수정
                    ex = ''.join(ex_li)                             # join()함수로 list를 다시 str으로 변환
                answer = min(max(calc(ex), answer), maximum)        # 계산 결과와 원래 값 중 최대값을 비교
                                                                    # 문제에서의 최대값을 넘어가지 않도록 비교
    print(answer)

Idea

1. 입력 예시 1을 기준으로 설명하겠다. 재귀 함수를 사용하면 더 쉬울 듯 하다.
   예를 들어 3+8*7-9*2 가 입력되면 3+8을 한 후 7-9*2를 재귀함수의 입력으로 넣고 다시 2를 입력으로 넣는 방식으로 풀어도 괜찮을 듯 한데 재귀함수를 많이 접하지 않아서 만들지 못했다.
2. 그래서 단순 반복으로 했는데 괄호가 들어갈 수 있는 위치의 모든 경우의 수를 구해야 했다. 우선 괄호의 최대 개수는 입력된 수식에서 연산자 개수를 2로 나눈 몫이다.
3. 괄호가 1개인 경우부터 최대 개수까지 반복해서 연산자의 개수에서 괄호 개수 만큼 가능한 모든 조합을 뽑아서 조건을 확인한다. 괄호 연산이 가능한 조건은 한 가지 뿐이다. 괄호 연산을 할 연산자가 붙어 있으면 안 된다.
4. 괄호 계산을 먼저 한 후 문자열에서 3글자를 한 숫자로 바꾸어주어야 했는데 str 형에서 문자를 대체하는 replace()함수로 구현을 하게 되면 바꾸려는 문자열과 같은 문자열이 더 앞에 존재하면 원하는 위치가 아니라 엉뚱한 문자열을 바꾼다.
   ex) 예제 입력 6에서 수식은 1-9-1-9-1-9-1-9-1-9 일 때
   1-9-1-9-(1-9)-1-9-1-9, 1-9-1-9-1-9-1-9-(1-9) 두 경우 모두 -8-1-9-1-9-1-9-1-9로 바뀐다.
   그래서 문자열로 표현된 수식을 잠깐 리스트로 바꿔서 원하는 위치의 문자들을 바꾼후 다시 str로 변환한다. 문자열로 바꿀 때는 전에 사용했던 ''.join()을 사용했다.
   ( 문자열은 튜플 같이 요소들의 직접적인 변경이 허용되지 않는다. ex) str[0] = 'a' error
5. 수식을 계산하는 함수 calc()를 살펴보면 연산자의 위치를 찾고 연산자가 나타날 때까지의 수를 operand로 사용해서 그 전의 값과 old_op에 해당하는 연산을 수행한다. 만약 연산자 뒤에 바로 -가 나오면 그건 음수를 뜻하는 것으로 if 문에서 False가 되어 동작하지 않는다.
6. 수식의 길이가 1인 경우와 3인 경우에는 괄호의 최대 개수가 0으로 되어 동작하지 않아서 처음에 예외 처리를 해두었다.

이번 코드는 재귀함수로 여러 번 시도하다가 안 돼서 시간이 오래 걸렸다. 이 문제에서 처음으로 사용한 함수는 eval()이라는 함수이다. 어떤 책에서는 괄호 안의 수식을 계산해주는 함수라고만 설명이 되어 있다. 하지만 eval()은 괄호 안에 파이썬 명령어를 써 넣으면 명령어에 해당하는 동작을 수행하고 그 값을 반환해준다.

s = "\"Hello World\""
eval("print(" + s + ")")

# 결과
# Hello World

내가 봐도 코드가 이해가 안 될 수 있는 부분들이 많아서 설명이 길어졌다. 더 클린한 코드를 짜도록 노력해야겠다.

[백준][파이썬] 16943번 숫자 재배치

문제 번호 : 16943
문제 출처 : https://www.acmicpc.net/problem/16943

Code

from itertools import permutations

def to_int(t):
    if t[0] != '0':
        pos = 10 ** (len(t)-1)
        tmp = 0
        for i in t:
            tmp += int(i) * pos
            pos = pos // 10
        return tmp
    return -1


a, b = input().split()
b = int(b)
c = -1

numbers = list(permutations(a)
for number in numbers:
    if number[0] == '0':
        continue
    num = int(''.join(number)) # to_int(number)
    if num < b:
        c = max(num, c)

print(c)

Idea

1. a를 순열을 사용해서 만들기 편하게 하기 위해서 int형으로 변환하지 않고 문자열로 입력받는다. (문자열도 iterable이기 때문에)
2. b는 미리 int형으로 형변환을 한다.
3. permutations(a) r 이 생략되었으므로 a의 길이를 인자로 갖는다.
4. 문자로 이루어져 있는 튜플을 숫자로 변환한다.
5. b와 비교해서 작으면 다시 max()로 비교한 후 저장한다.

for 문에서 number 가 튜플 자료형이기 때문에 int(number)를 사용할 수 없어서 처음에는 to_int()라는 함수를 만들어서 사용했다. 그러다가 튜플을 문자열로 바꾸는 방법이 있어서 적용해봤다. 내가 만든 to_int()로 프로그램을 돌렸을 때 시간이 1288ms 가 나왔고 int(''.join(number))를 사용했을 때 432ms 가 나왔다.

''.join(iterable) 은 iterable 자료형의 값들을 모두 이어붙여서 반환해준다. 값들 사이에 문자를 넣고 싶다면 따옴표 사이에 넣으면 된다. 예를 들어'-'.join(['a', 'b','c']) 라는 함수가 있으면 'a-b-c'를 반환한다.

문제 번호 : 16938

문제 출처 : https://www.acmicpc.net/problem/16938 

Code

import itertools


def diff(num):
    return max(num) - min(num)


n, l, r, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

for i in range(2, n+1):
    numbers = list(itertools.combinations(a, i))
    for number in numbers:
        if l <= sum(number) <= r:
            if diff(number) >= x:
                count += 1

print(count)

Idea

1. N개의 난이도를 2개 이상으로 조합해서 조건에 맞는지 확인한다.
2. combination한 후 list의 요소는 iterable한 튜플 형으로 모든 난이도의 합은 sum 함수로 구현이 가능하다.
3. 차를 구하는 함수는 최대값에서 최소값을 빼주는 형태로 가능했다.
4. 두 조건을 모두 만족하면 count 값을 1씩 증가시키고 마지막에 출력한다.

이전의 문제들보다 난이도가 낮은 편이었다. 처음에는 n이 1인 경우에 print(0)을 먼저 하는 경우를 생각했었는데 print를 2번하게 되어서 채점중(99%)에서 "틀렸습니다"가 나왔다. 아무래도 마지막 입력에서 n이 1인 듯하다. n이 1이면 2개 이상을 조합으로 뽑아올 수 없다.

문제 번호 : 16936

문제 출처 : https://www.acmicpc.net/problem/16937

Code

import sys


def able(height, width, row, col):
    if row <= height and col <= width:
        if row <= width and col <= height:
            return 3
        else:
            return 1
    elif row <= width and col <= height:
        return 2
    else:
        return 0


h, w = map(int, input().split())
n = int(input())
stickers = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
result = 0

for i in range(len(stickers)):
    r, c = stickers[i][0], stickers[i][1]
    way = able(h, w, r, c)
    if way > 0:
        if way == 1:
            new_hw = [h-r, w, h, w-c]
        elif way==2:
            new_hw = [h-c, w, h, w-r]
        else:
            new_hw = [h-r, w, h, w-c, h-c, w, h, w-r]

        for sticker in stickers[i+1:]:
            new_r, new_c = sticker[0], sticker[1]
            for j in range(0, len(new_hw), 2):
                if able(new_hw[j], new_hw[j+1], new_r, new_c) > 0:
                    result = max(r*c + new_r * new_c, result)
print(result)

Idea

1. 스티커의 한 변의 길이가 모눈종이의 높이보다 작거나 같고 다른 한 변의 길이가 모눈종이의 너비보다 작거나 같으면 스티커를 모눈 종이에 붙일 수 있다.
   단순히 붙일 수 있는지 확인하는 것은 max(r, c) < max(h, w) and min(r, c) < min(h, w) 로 구현하면 된다.
2. 붙일 수 있는 스티커면 일단 붙인다.
   

   

3.  1번 영역에 스티커가 붙어 있으면 2번 영역 + 4번 영역, 3번 영역 + 4번 영역 두 가지 위치에 붙일 수 있다.
   따라서 이 때 새로운 크기를 가진 모눈 종이가 생긴다고 생각한다.
   이 새 모눈 종이들의 높이와 너비를 new_hw 리스트에 저장한다.
4. 현재 붙은 스티커 이후의 스티커들이 새 모눈 종이에 붙일 수 있는지를 판별하고 그 때의 넓이가 더 커지면 result를 갱신한다. 

처음에는 stickers를 넓이를 기준으로 내림차순으로 정렬한 후 두 스티커가 붙게 되면 무조건 최대값이니까 break문을 사용해서 최대한 반복문을 덜 돌게 하려고 노력했고 입력 예제 입력들은 모두 통과가 되는데 코드 제출하니까 "틀렸습니다."라고 나왔다.