BOJ_17836 공주님을 구해라! -Python3

문제분석

1. 관찰
- bfs로 공주에게 도달하는 시간을 구한다.
- 그람까지 bfs + 벽을 무시하고 공주에게 도달하는 최단거리를 구한다.
- !! 그람을 발견하면 공주와의 거리는 사칙연산으로 구할 수 있다. 시간복잡도를 줄이자.
- 둘 중의 작은 값이 T보다 작으면 최소값 출력
- 구출하지 못하는 경우 fail

2. 복잡도
- O(N*M) = 100*100 >> 1만 가능

3. 자료구조
- 성 int[][]
- 방문여부 int[][]

해결코드

import sys
from collections import deque
si = sys.stdin.readline

N, M, T = map(int, si().split())
castle = [list(map(int, si().split())) for _ in range(N)]
check = [list(0 for _ in range(M)) for _ in range(N)]

q = deque()
q.append((0,0,0))
result = float('inf')
while q:
    x, y, t = q.popleft()
    if x == M-1 and y == N-1: # 공주위치 도착
        result = min(result, t)
        break
    if t+1>T: #시간초과
        break 
    for i,j in [(-1,0),(1,0),(0,-1),(0,1)]:
        nx, ny = x + i, y + j
        if 0 <= nx < M and 0 <= ny < N and not check[ny][nx]:
            if castle[ny][nx] ==1:
                continue
            elif castle[ny][nx]==0:
                check[ny][nx]=1
                q.append((nx,ny,t+1))
            else:    
                check[ny][nx]=1
                gramT = t + 1 + abs((N-1)-ny) + abs((M-1)-nx)
                if gramT<=T: 
                    result=gramT


if result>T: 
    print("Fail")
else:
    print(result)

BOJ_15787 기차가 어둠을 헤치고 은하수를 -Python3

문제분석

1. 관찰
- 명령에 따라 기차 좌석을 조절해준다.
- 패스한 기차를 기록하여 이후 기차를 보낼지 판단한다.

2. 복잡도
- O(N+M) = 20만 >> 가능

3. 자료구조
- 명령 list[][]
- 패스한 기차 : list[]

해결코드

import sys
si = sys.stdin.readline

N, M = map(int, si().split())
m_list = list(list(map(int, si().split())) for _ in range(M))

train_list = [[0]*20 for _ in range(N)] # 처음기차에는 아무도 타지 않는다
pass_train = []

for m in m_list:
    m_num, i = m[0], m[1]-1
    t = train_list[i]

    if m_num ==1:
        x = m[2]-1
        if t[x] == 0:
            t[x] = 1

    elif m_num ==2:
        x = m[2]-1
        if t[x] == 1:
            t[x] = 0

    elif m_num ==3:
        t[:] = [0]+t[:-1]

    elif m_num ==4:
        t[:] = t[1:]+[0]

ans = 0
for i in range(N):
    if train_list[i] not in pass_train:
        pass_train.append(train_list[i])
        ans+=1

print(ans)

BOJ_15649 N과 M (1) - Python3

문제 접근

1. 아이디어
- 백트래킹 재귀함수 안에서 for loop를 돌면서 숫자 선택 & 방문여부 확인
- 재귀함수에서 M개를 선택할 경우 print

2. 복잡도
- N! > 가능(8까지 가능)

3. 자료구조
- 결과값 저장 int[]
- 방문여부 체크 bool[]

해결 코드 1

import sys
input = sys.stdin.readline

N,M = map(int, input().split())
result = []
check = [False]*(N+1)

def recur(num):
    if num == M:
        print(' '.join(map(str, result)))
        return
    for i in range(1, N+1):
        if check[i] == False:
            check[i] = True # 방문
            result.append(i)
            recur(num+1)
            check[i] = False
            result.pop()

recur(0)

해결 코드 2

import sys
si = sys.stdin.readline

N, M = map(int, si().split())

s = []
def f():
    if len(s) == M:
        print(' '.join(map(str,s)))
        return

    for i in range(1,N+1):
        if i in s:
            continue
        s.append(i)
        f()
        s.pop()
f()

같은 풀이이지만 방문여부를 코드 2 처럼 판별하면 코드가 간결해진다.

BOJ_15686 치킨 배달 - Python3

문제 분석

1. 관찰
- 전체 치킨 집에서 중복없이 M 개의 치킨집을 선택하여 탐색
- combinations를 통해 m개 선택한 경우에 대하여 최소값의 합을 구한다.

2. 복잡도
- O(N*N) = 50*50 상수배 >> 가능

3. 자료구조
- 집, 치킨집: int[]
- 거리합 : int

해결 코드

import sys
si = sys.stdin.readline
from itertools import combinations

N, M = map(int, si().split())

h = [] # 집의 위치
c = [] # 치킨집의 위치

for i in range(N):
    tmp = list(map(int, si().split()))
    for j in range(N):
        if tmp[j] == 1:
            h.append([i,j])
        if tmp[j] == 2:
            c.append([i,j])


ans = float("inf")

for chicken in combinations(c, M):
    sum = 0
    for hou in h:
        sum += min([abs(hou[0]-chi[0])+abs(hou[1]-chi[1]) for chi in chicken])
    if ans>sum:
        ans = min(ans, sum)
print(ans)

BOJ_16918 봄버맨

문제 분석

1. 관찰
- 첫 번째 폭탄이 터진 형태와 두 번째 폭탄이 터진 형태가 3번째 부터 반복된다.
- 첫 폭탄 폭파 3,7,11...
- 둘째 폭탄 폭파 5,9,14...
... 코드 참고

2. 복잡도
- O(R*C) = 200*200*8 >> 가능

3. 자료 구조
- 폭탄 배열: int[][]

해결 코드

import sys
si = sys.stdin.readline

R, C, N = map(int, si().split())
board = [list(si().strip()) for _ in range(R)]


if N<=1: # 첫 1초동안은 인풋을 출력
    for li in board: print(''.join(li))
elif N%2 == 0: # 짝수번째는 폭탄이 모두 차 있는 형태
    for i in range(R): print('O'*C)
else: # 첫 폭탄이 터진 이후 3번째 부터 형태가 반복된다. 3,7,11 ... 과 5,9,13...

    bom_1 = [["O"]*C for _ in range(R)] # 첫 폭탄 터짐
    for i in range(R):
        for j in range(C):
            if board[i][j] == "O":
                for y, x in [(0, 0),(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    ny, nx = y+i, x+j
                    if 0 <= ny < R and 0 <= nx < C:
                        bom_1[ny][nx] = '.'

    bom_2 = [["O"]*C for _ in range(R)] # 두 번째 폭탄 터짐
    for i in range(R):
        for j in range(C):
            if bom_1[i][j] == "O":
                for y, x in [(0, 0),(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    ny, nx = y+i, x+j
                    if 0 <= ny < R and 0 <= nx < C:
                        bom_2[ny][nx] = '.'

    if N%4==3:
        for li in bom_1: print(''.join(li))
    if N%4==1:
        for li in bom_2: print(''.join(li))

BOJ_20115 에너지 드링크

문제 분석

1. 관찰
- 최대로 만들 수 있는 에너지 드링크의 양은
- 직관적으로 가장 큰 값을 a로 선택하고 나머지 음료들의 절반을 다 더한 값과 같음을 알 수 있다.

2. 복잡도
- max() = O(N)
- sum() = O(N)
>> 100000 + 100000 >> 가능

3. 자료구조
- int

해결 코드

import sys
si = sys.stdin.readline

N = int(si())
drinks = list(map(int, si().split()))

M = max(drinks)
S = sum(drinks)

print(M+(S-M)/2)