문제

난이도	번호	문제 이름
	1072	게임
	15728	에리 - 카드
	17485	진우의 달 여행 (Large)
	18430	무기 공학

HOW TO SOLVE

• 게임 : 이진 탐색
• 무기 공학 : 백트래킹
• 에리-카드 : 단순 구현 + 브루트포스
• 진우의 달 여행 : DP (BFS는 시간초과)

게임

# 키워드 : 형택이는 앞으로의 모든 게임에서 지지 않는다 -> 추가 판수는 모두 이긴것으로 간주한다.
# Z = (Y * 100) // X로 작성. (Y // X) * 100으로 작성하면 오류가 발생한다. -> 부동소수점 오차 때문에
# 승률 Z가 99이상인 경우에는 아무리 이겨도 더 이상 승률이 변하지 않는다.
# 최소 몇판을 해야 하는지 구해야 한다
# 1 ≤ X ≤ 1,000,000,000
import sys
input = sys.stdin.readline

# 이진탐색
def binary_search(x):
    l, r = 0, x
    answer = 0
    
    while l <= r:
        mid = l + (r - l) // 2 # 중간값
        ratio = (y + mid) * 100 // (x + mid) # 새로운 승률
        
        # 새로운 승률이 기존 승률보다 크다면
        if ratio > z:
            answer = mid # 정답 갱신 
            r = mid - 1 # 최소 판수로 줄일 수 있으므로 왼쪽 부분 탐색
        else:
            l = mid + 1 # 오른쪽 부분 탐색
            
    return answer

x, y = map(int, input().split()) # x : 게임 횟수, y : 이긴 게임 수
z = y * 100 // x # 기존 승률

if z >= 99: print(-1) # 승률 변하지 않음
else:
    ret = binary_search(x)
    print(ret)

X의 범위가 10억으로 상당히 크다. 선형 탐색을 사용하면 당연히 시간초과가 발생한다.
이렇게 큰 범위가 주어지면 이진 탐색(이분 탐색) 을 생각해보자.

에리-카드

# 상대는 항상 최선의 방법으로 팀 숫자카드의 카드를 제거한다.
# N, K(0 ≤ K < N ≤ 100)

n, k = map(int, input().split())
share_cards = list(map(int, input().split())) # 공유 숫자카드
team_cards = list(map(int, input().split())) # 팀 숫자카드

# 카드 견제하기
for _ in range(k):
    _max = -int(1e9) # 최대 점수
    pick = 0 # 상대가 선택한 카드
    
    for share in share_cards:
        for team in team_cards:
            if _max <= share * team: # 최대 점수라면
                _max = share * team 
                pick = team # 카드 선택
                
    team_cards.remove(pick) # 상대가 선택한 카드 제거

_max = -int(1e9) # 최대 점수
for share in share_cards:
    for team in team_cards:
        _max = max(_max, share * team) # 최대 점수 갱신

print(_max)

N과 K의 범위가 100이하 이므로, $O(N^2)$도 충분히 가능하다.

진우의 달 여행

실패 코드

# Sol 1 - BFS
# 왼쪽 대각선 아래, 수직 아래, 오른쪽 대각선 아래 => 0, 1, 2
dx, dy = [1, 1, 1], [-1, 0, 1]
INF = int(1e9)

# BFS - 인접 행렬 사용
def bfs():
    q = deque()
    for i in range(m):
        q.append((0, i, -1))  # (x, y, 움직인 방향)
        dist[0][i] = graph[0][i]  # 시작점의 소모 연료

    while q:
        x, y, d = q.pop()

        for i in range(3):
            nx, ny = x + dx[i], y + dy[i]

            # 범위 내에 있을 때
            if 0 <= nx < n and 0 <= ny < m:
                # 이전 방향이 아닐 때
                # 같은 방향으로 두번 연속으로 움직일 수 없는 조건 처리
                if d != i and dist[x][y] + graph[nx][ny] < dist[nx][ny]:
                    dist[nx][ny] = dist[x][y] + graph[nx][ny]  # 최솟값 갱신
                    q.append((nx, ny, i))  # (x, y, 움직인 방향) 추가


n, m = map(int, input().split())  # 행렬의 크기 N * M

graph = [list(map(int, input().split())) for _ in range(n)]

dist = [[INF] * m for _ in range(n)]

bfs()

print(min(dist[n - 1]))

인접행렬로 구현한 BFS이다.
인접행렬로 구현한 BFS의 시간복잡도는 $O(V^2)$ 이다.

이때 V는 노드의 개수이고, 이 문제에서는 N을 의미한다.
하지만 이 코드의 시간복잡도는 $O(N^2)$는 아니다.

문제의 조건을 잘 살펴보면 하나의 행에서 양 끝의 칸은 아래 갈래로 뻗어나갈 때 2가지 경우의 수가 존재한다.
그리고 양 끝이 아닌 칸들은 3가지 경우의 수가 존재한다.

즉, 한 행에서 열이 M개라면, $2 * 2 + (3 * 3 * 3 ... * 3)$ 으로 $2^2 + 3^{(M-2)}$ 이다.

이때 행의 개수는 N개이므로 총 시간복잡도는,
$(4 + 3^{M-2})^N = O(3^{MN})$로 표현할 수 있다.

문제에서 N과 M은 최대 1000까지 가능하므로,
이 코드는 시간초과를 하고도 남는다.

성공 코드

# Sol 2 - DP
INF = int(1e9)
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

dp = [[[INF] * 3 for _ in range(m)] for _ in range(n)]

for i in range(m):
    for j in range(3):
        dp[0][i][j] = graph[0][i]

for i in range(1, n):
    for j in range(m):
        if j == 0: # 왼쪽 끝일 때
            # 오른쪽 대각선 아래 존재하지 않음
            dp[i][j][0] = min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + graph[i][j]
            dp[i][j][1] = dp[i - 1][j][0] + graph[i][j]
        elif j == m - 1: # 오른쪽 끝일 때
            # 왼쪽 대각선 아래 존재하지 않음
            dp[i][j][1] = dp[i - 1][j][2] + graph[i][j]
            dp[i][j][2] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + graph[i][j]
        else:
            dp[i][j][0] = min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + graph[i][j]
            dp[i][j][1] = min(dp[i - 1][j][0], dp[i - 1][j][2]) + graph[i][j]
            dp[i][j][2] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + graph[i][j]

_min = INF
for i in range(m):
    _min = min(_min, min(dp[n - 1][i]))
print(_min)

이 코드의 시간복잡도는 $O(NM)$이다.
N과 M이 최대 1000까지 가능함을 고려했을 때, 100만으로 충분히 통과할 수 있다.
단, 점화식을 잘 세워야 한다.

무기 공학

# (0, 0) 부터 시작해서 (0, m - 1)까지 탐색
# (0, m - 1)까지 탐색이 끝나면 (1, 0)부터 시작해서 (1, m - 1)까지 탐색
# 이런 식으로 n - 1 행 까지 반복

# 백트래킹
def helper(x, y, _sum):
    global _max
    # 다음 행으로 갱신
    if y == m:
        x += 1
        y = 0
        
    # 행 탐색도 끝나면 종료
    if x == n:
        _max = max(_max, _sum)
        return
    
    # (x, y)를 방문하지 않은 경우
    if not visited[x][y]:
        # 부메랑 모양 만들기
        for i in range(4):
            a, b, c, d = shape[i]
            nx1, ny1, nx2, ny2 = x + a, y + b, x + c, y + d # 부메랑 좌표
            if is_range(nx1, ny1) and is_range(nx2, ny2) and not visited[nx1][ny1] and not visited[nx2][ny2]: # 부메랑이 범위에 포함되는 경우
                visited[x][y] = visited[nx1][ny1] = visited[nx2][ny2] = 1 # 다음 경우의 수를 위해 방문처리
                helper(x, y + 1, _sum + graph[x][y] * 2 + graph[nx1][ny1] + graph[nx2][ny2]) # 재귀 호출
                visited[x][y] = visited[nx1][ny1] = visited[nx2][ny2] = 0 # 방문처리 해제
    
    # 이미 (x, y)를 방문한 경우
    helper(x, y + 1, _sum)
    
def is_range(x, y):
    return 0 <= x < n and 0 <= y < m

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
shape = {0 : (0, -1, 1, 0), 1 : (-1, 0, 0, -1), 2 : (-1, 0, 0, 1), 3 : (0, 1, 1, 0)}
_max = 0

helper(0, 0, 0)

print(_max)

백트래킹을 이용하는 문제이다.
단순 for문도 될 것 같긴 한데, 처음에 문제를 봤을 때 n과m의 범위가 최대로 5여서 백트래킹이 떠올랐다.
(떠오르기만 했다)

다른 사람의 코드를 참고했다.

shape 변수는 가능한 부메랑 모양 4가지의 중심을 제외한 나머지 칸의 좌표를 구할 때 필요한 좌표들을 담고있다.
helper() 에서 인자로 받는 x, y가 부메랑의 중심 좌표이다.

알고리즘은 일반적인 백트래킹과 유사하다.
먼저, (0, 0)에서 시작해서 (0, m - 1)까지 탐색을 진행한다.
만약, (0, m - 1)까지 진행을 완료했으면 다음 행으로 넘어가 다시 탐색한다.

즉, 진행방향은 왼쪽 위 에서 부터 시작해서 오른쪽 아래 로 진행해간다.

종료 조건은 x == n 일 때 이다.

메인 흐름은 다음과 같다.

1. 만약 (x, y)를 방문한 적이 없다면, 부메랑 모양을 만들어준다(=좌표를 만들어 주는 것)
2. 부메랑을 이루는 좌표들이 범위 내에 있고 모두 방문한 적이 없다면, 방문처리를 해주고 재귀호출한다.
3. 그리고 마지막으로는 다음 경우의 수를 위해서 방문처리를 해제한다.
4. 만약, (x, y)를 방문했었다면 해당 좌표를 넘기고 진행한다.(=열 우선 진행이므로 (x, y + 1)로 재귀호출)