중요 팁

ctrl+alt+L : 보기 좋게 정렬

백준 1966

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
for _ in range(N):
    result = []
    n, m = map(int, input().split())
    print_q = deque(map(tuple, enumerate([*map(int, input().strip().split())])))
    # print(print_q)

    # remaining items classified for importance
    print_li = [0] * 11
    for i in print_q:
        print_li[i[1]] += 1

    while print_q:
        if sum(print_li[print_q[0][1] + 1:]) > 0:
            # print("print_q: ", print_q)
            print_q.append(print_q.popleft())
        else:
            a = print_q.popleft()
            print_li[a[1]] -= 1
            result.append(a)
    for idx, ele in enumerate(result):
        if ele[0] == m:
            print(idx + 1)

입력을 다 받고 출력하자!

백준 15686

치킨 배달 문제

import sys
from itertools import combinations


def in_index(t):
    if 0 <= t[0] < N and 0 <= t[1] < N:
        return True
    return False


def searching(t):
    for n in range(1, 2 * N - 1):
        start = [t[0] - n, t[1]]
        for i in range(4):
            for _ in range(n):
                if in_index(start):
                    if arr[start[0]][start[1]] == 3:
                        return n
                start[0] += move_li[i][0]
                start[1] += move_li[i][1]
                #print("start :", start)


input = sys.stdin.readline

INF = 99999999999
N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append([*map(int, input().split())])

# counter clockwise
move_li = ((1, -1), (1, 1), (-1, 1), (-1, -1))

# checking customer
cus_li = []
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            cus_li.append((i, j))
# checking chicken
chicken_li = []
for i in range(N):
    for j in range(N):
        if arr[i][j] == 2:
            chicken_li.append((i, j))

# getting a combination (M of the number of chicken sellers)
combi = list(combinations(range(len(chicken_li)), M))

# 조합에 의해 선택된 치킨집을 3으로 만들어서 최단 거리 계산에 이용한다
result = INF
for i in combi:
    for j in range(M):
        row, col = chicken_li[i[j]]
        arr[row][col] = 3

    r = 0
    for k in cus_li:
        r += searching(k)
    result = min(result, r)

    # 다시 원래대로 3을 2로
    for k in arr:
        for j in range(N):
            if k[j] == 3:
                k[j] = 2


print(result)

우수 코드

import sys
N,M = map(int,sys.stdin.readline().split())
city = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
house = []
chicken = []
for i in range(N):
  for j in range(N):
    if city[i][j] == 2:
      chicken.append((i,j))
    elif city[i][j] == 1:
      house.append((i,j))

chicken_distance = []
for i in range(len(house)):
  chicken_distance.append([])
  for j in range(len(chicken)):
    chicken_distance[-1].append((abs(house[i][0]-chicken[j][0]) + abs(house[i][1]-chicken[j][1]),j))
  chicken_distance[-1].sort(key = lambda x: x[0])

ans = 1000000000
def city_chicken_distance():
  global ans
  a = 0
  for i in chicken_distance:
    for j in i:
      if j[1] in survived:
        a += j[0]
        break
    if a >= ans:
      return
  ans = min(ans,a)

def open(M,n):
  if M == 0:
    city_chicken_distance()
  for i in range(n,len(chicken)):
    if i not in survived:
      survived.add(i)
      open(M-1,i+1)
      survived.remove(i)

survived = set()
open(M,0)

print(ans)

결과

정답처리는 됐지만 실행시간 조건을 만족하지 못했다. 아마 1초까지면 2초 직전까지는 정답처리를 해주는 것 같다.

brute forcing에서 순열이나 조합을 이용해야 하는 문제가 자주 보이는데 itertools를 이용하면 아슬아슬하거나 시간 초과할 가능성이 높다. 이런 경우 어떻게 처리해야 하는지를 위 코드가 잘 보여주고 있다.