[백준][파이썬] 15686번 치킨 배달

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

Code

import sys
from itertools import combinations

## 입력
n, m = map(int, input().split())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

distance = []   # 집 별로 치킨 집과의 거리 저장
chickens = []   # 치킨 집의 위치와 치킨 집의 번호 저장
houses = []     # 집의 위치 저장
n_chicken = 0
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houses.append([i, j])
        elif city[i][j] == 2:
            chickens.append([i, j, n_chicken])
            n_chicken += 1

for i in range(len(chickens)):
    distance.append([])
    for house in houses:
        distance[i].append(abs(chickens[i][0] - house[0]) + abs(chickens[i][1] - house[1]))

cases = combinations(chickens, m)

answer = 1e9

for case in cases:
    d = []
    for i in range(m):
        d.append(distance[case[i][2]])

    d = list(map(min, zip(*d)))
    answer = min(sum(d), answer)

print(answer)

Idea

1. N x N 크기의 배열을 모두 탐색하면서 집의 위치와 치킨 집의 위치를 모두 저장
2. 치킨 집의 위치를 저장할 때에는 치킨 집의 number를 차례로 부여
3. 집마다 각 치킨집과의 거리를 저장
4. 치킨 집의 갯수에서 M개의 조합을 생성
5. M개의 조합을 모두 탐색하며 치킨 거리가 최소인 답을 구함

이번 문제에서 zip 함수와 map 함수, 그리고 * 을 사용해서 각 거리들 중 최단 거리를 구했다.
d = list(map(min, zip(*d))) 를 해석해보겠다.
iterable앞에 *을 붙이게 되면 iterable형의 요소들을 모두 반환한다.
예시를 들자면 다음과 같다.

def print_all(a, b, c):
    print(a)
    print(b)
    print(c)

li = [1, 2, 3]
print_all(*li)

### 실행결과
# 1
# 2
# 3

코드에서 d 는 2차원 리스트이므로 여러 개의 1차원 리스트들을 반환한다.
zip함수는 여러개의 iterable이 입력으로 들어오면 index가 같은 요소들끼리 튜플로 합쳐서 반환한다. d의 각 1차원 리스트들은 각 집에서 치킨집들까지의 거리이고 zip함수를 사용하고 나면 각 치킨 집마다의 집들까지의 거리가 된다.
여기에 map함수로 각 리스트별로 min함수를 사용해서 리스트로 반환한다.
처음에 2차원 배열을 모두 돌면서 각 치킨집 별로 최소 거리를 구하는 방법을 사용했고 시간이 400ms가 나왔다. 그런 과정을 저 한 줄의 코드로 변환해서 확인한 결과 112ms로 시간이 많이 줄어들었다.

[백준][파이썬]

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

Code

# 등차 수열이려면 첫 번째 차와 두 번째 차가 같은 경우여야 함

n = int(input())
a = list(map(int, input().split()))

if n < 3:  # 숫자가 하나 또는 2개면 무조건 등차수열
    print(0)
else:
    diff = []   # 수열에서 한 칸당 차이를 저장
    for i in range(n - 1):
        diff.append(a[i] - a[i + 1])
    if len(set(diff)) == 0: # 차이가 모두 같으면 집합으로 했을 때 값이 하나밖에 없다.
        print(0)
        exit(0)

    op = (-1, 0, 1)     # 연산의 종류
    cases = []
    answer = n + 1      # 최소값을 찾을 거고 값은 연산횟수는 n을 넘어갈 수 없다.
    for i in op:
        for j in op:
            for k in op:
                count = abs(i) + abs(j) + abs(k)
                d1, d2 = diff[0] + i - j, diff[1] + j - k
                if d1 == d2:    # 0번와 1번, 1번와 2번의 차가 같은 경우 cases에 저장
                    cases.append((a[0] + i, d1, count))

    for case in cases:      # 저장된 케이스들만 생각
        start = case[0]
        sub = case[1]
        cnt = case[2]
        if n == 3:          # A3까지 모두 연산을 해봤기 때문에 길이가 3인 경우 답은 cnt일 확률이 높다.
                            # 아닌경우도 있을 듯
            answer = min(answer, cnt)
        for idx in range(3, n):
            tmp = a[idx] - (start - (sub * idx))    # idx 번째의 값이 예상 값보다 1 이상 차이나면
            if abs(tmp) > 1:                        # +-1 연산만으로 등차수열을 만들 수 없다.
                break
            elif abs(tmp) == 1:                     # 값이 1밖에 차이 안나면 +든 -든 연산을 해야된다.
                cnt += 1                            # 뭘할지 정할 필요는 없고 횟수만 세면 된다.
            if idx == n - 1:
                answer = min(answer, cnt)

    print(answer if answer <= n else -1)            # answer가 n+1이면 -1을 출력, 아니면 answer를 출력

Idea

1. 입력된 수가 2개 이하이면 항상 등차수열이 된다. 그런 경우 연산을 0번 진행하기 때문에 print(0)를 하고 프로그램을 종료한다.
2. 입력된 수가 3개 이상인 경우를 생각해보면 A1, A2, A3 에 각각 연산을 한 후 A1 - A2 과 A2-A3가 같아지는 경우들만 cases에 추가해준다. 이 때 연산 횟수는 -1, 1 은 각 한 번씩, 0은 연산을 하지 않은 것으로 생각하기 위해서 절대값을 취해줬다.
3. cases에 추가된 경우들에서 4번 째 수부터 첫 번째 수와 차를 이용해서 구한 예상값과 차이가 1보다 크면 등차수열이 만들어질 수 없다.
4. 예상값과 차이가 1이면 연산횟수를 1 더해주고 0이면 그냥 넘어간다. 마지막 수까지 예상값과 차이가 1 이하이면 answer에 cnt의 최소값을 넣어준다.
5. 처음에 answer = n + 1 로 정의했기 때문에 등차수열을 만들 수 있는 case가 존재하지 않으면 answer > n 이기 때문에 -1을 출력하도록 한다.

[백준][파이썬] 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'를 반환한다.