그냥 코딩하는 사람의 블로그

https://www.acmicpc.net/problem/2503

풀이 과정

1. 가능한 모든 경우의 수 리스트를 만든다.
   • 이 때, 자릿수를 하나하나 떼서 리스트로 만드는게 비교가 훨씬 편하다.
   • [[1, 2, 3], [1, 2, 4], ... ]
2. (1)에서 만든 리스트의 요소들을 하나씩 꺼내서 질문과 비교해 본다.
   1. 현재 요소가 정답이라고 가정한다. ex) [1, 2, 3]
   2. 정답이 [1, 2, 3]일때, 질문에 해당하는 스트라이크와 볼의 개수를 구하고 실제로 답한 스트라이크와 볼의 개수와 비교해 본다.
   3. 다르다면 현재 요소는 정답이 아닌 것이므로 다음 요소를 검사한다. ex) [1, 2, 4]
   4. 모든 질문에 대해 구한 결과와 답한 결과가 같다면, 가능성이 있는 답이므로 정답 카운트를 하나 늘려준다.
3. 정답 카운트를 출력시킨다.

소스 코드

import sys
import heapq


sequence = [(i, j, k)
            for i in range(1, 10)
            for j in range(1, 10)
            for k in range(1, 10)
            if i != j and j != k and i != k]

n = int(sys.stdin.readline().rstrip())
num_list = []
strike_list = []
ball_list = []
for _ in range(n):
    num, strike, ball = map(int, sys.stdin.readline().rstrip().split())
    num_list.append(list(map(int, list(str(num)))))
    strike_list.append(strike)
    ball_list.append(ball)

answer = 0

for x, y, z in sequence:
    for i in range(n):
        strike_count = 0
        ball_count = 0
        # 같은 위치에 값도 같은 경우 strike
        # 다른 위치에 있는 경우는 ball
        if num_list[i][0] == x:
            strike_count += 1
        else:
            if num_list[i][0] == y or num_list[i][0] == z:
                ball_count += 1
                
        if num_list[i][1] == y:
            strike_count += 1
        else:
            if num_list[i][1] == x or num_list[i][1] == z:
                ball_count += 1
                
        if num_list[i][2] == z:
            strike_count += 1
        else:
            if num_list[i][2] == y or num_list[i][2] == x:
                ball_count += 1

        if strike_count != strike_list[i] or ball_count != ball_list[i]:
            break
    else:
        answer += 1

print(answer)

https://www.acmicpc.net/problem/1238

풀이 과정

1. 단방향 그래프이므로 시작점을 X를 제외한 모든 점에서 다익스트라 알고리즘을 진행해보아야 한다.
   1. 시작하기 전에, X점에서 다익스트라 알고리즘을 적용하여 X점에서 각각의 점 사이의 최단 경로를 구해준다. 최단 경로 리스트를 X_to_S라고 둔다.
   2. 이후, i점에서 다익스트라 알고리즘을 사용하여 X점까지의 거리를 구한 다음, X점에서 다시 i점으로 돌아가야 하므로 X_to_S[i]를 더해준 다음 정답을 갱신시켜 준다.
2. 다익스트라 알고리즘의 경우 거리가 가장 짧은 노드를 선택할 때 최소 히프를 사용해 주면 조금 더 빠르게 풀이를 할 수 있다.
3. 최종적으로 갱신된 정답을 출력한다.

소스 코드

import sys
import heapq

INT_MAX = int(10e9)

input = lambda: sys.stdin.readline().rstrip()
N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    s, e, t = map(int, input().split())
    graph[s].append([e, t])

def dijkstra(X):
    heap = []
    time = [INT_MAX] * (N+1)
    time[X], time[0] = 0, 0
    heapq.heappush(heap, [0, X])

    while heap:
        curr_time, city = heapq.heappop(heap)
        if curr_time != time[city]:
            continue
        for e, t in graph[city]:
            if time[e] > t + curr_time:
                time[e] = t + curr_time
                heapq.heappush(heap, [time[e], e])

    return time

X_to_S = dijkstra(X)
answer = 0
for i in range(1, N+1):
    if i == X: continue
    answer = max(answer, dijkstra(i)[X] + X_to_S[i])

print(answer)

https://www.acmicpc.net/problem/16236

풀이 과정

1. 현재 아기 상어의 위치를 찾아 두고, 아기 상어의 위치를 조정해주는 방식으로 진행하면 된다.
2. 다음에 사냥할 물고기는 BFS를 통해서 찾아준다.
   1. 단, 이 때 현재 아기 상어의 크기보다 큰 물고기로는 이동 불가능, 크기와 같은 물고기는 이동은 가능하지만 사냥 불가능한 점에 유의해서 BFS 수행
   2. 사냥 가능한 물고기가 등장하게 되면, 이동 길이를 저장해 두고 이동 길이가 같으면서 사냥 가능한 물고기가 또 있는지 찾아본다.
   3. 사냥 가능한 물고기 리스트를 행 기준으로 1차 정렬, 열 기준으로 2차 정렬해 준다. ( 거리는 모두 같으므로 고려할 필요 없이 좌표상 맨 위에 있어야 하며, 같은 행인 경우는 맨 왼쪽에 있어야 하므로 )
   4. 정렬된 물고기 리스트의 첫번째 요소가 사냥할 물고기의 위치이다.
3. 상어의 위치를 사냥할 물고기의 위치로 이동시키고, 이동 거리를 더해준다.
4. 상어의 현재 크기에서 사냥한 물고기의 수가 현재 크기가 된다면 상어의 크기를 하나 올려주고 사냥한 물고기 수를 0으로 초기화시켜 준다.
5. 사냥이 불가능할 때까지 2-4 과정을 반복한다.
6. 누적 이동 거리를 출력시켜 준다.

소스 코드

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()

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

# row, col, level
babyshark = [0, 0, 2]

for i in range(n):
    for j in range(n):
        if matrix[i][j] == 9:
            babyshark[0], babyshark[1] = i, j

def get_next_fish(babyshark):
    global n
    queue = deque([[babyshark[0], babyshark[1], 0]])
    visited = set()
    visited.add((babyshark[0], babyshark[1]))
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    minimum = int(10e9)
    candidate = []
    while queue:
        x, y, mv = queue.popleft()
        if mv == minimum:
            break
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < n and 0 <= ny and ny < n and \
               (nx, ny) not in visited and \
               matrix[nx][ny] <= babyshark[2]:
                queue.append([nx, ny, mv+1])
                visited.add((nx, ny))
                if matrix[nx][ny] != 0 and matrix[nx][ny] != 9 and \
                   matrix[nx][ny] < babyshark[2]:
                    minimum = mv+1
                    candidate.append([nx, ny])
    if candidate:
        candidate.sort(key=lambda x:(x[0], x[1]))
        return candidate[0][0], candidate[0][1], minimum
    else:
        return -1, -1, minimum
    

    
time = 0
eat_count = 0
while True:
    x, y, dist = get_next_fish(babyshark)
    if x == -1 and y == -1:
        break
    time += dist
    matrix[babyshark[0]][babyshark[1]] = 0
    babyshark[0], babyshark[1] = x, y
    matrix[babyshark[0]][babyshark[1]] = 9
    eat_count += 1
    if eat_count == babyshark[2]:
        babyshark[2] += 1
        eat_count = 0

print(time)

https://www.acmicpc.net/problem/1799

풀이 과정

1. 핵심은 격자를 흰칸 격자, 검은칸 격자로 나누어서 보아야 한다는 점
   1. 격자의 크기가 10x10을 통째로 보게 된다면 다 한번씩 둬봐야 하므로 시간초과가 걸리게 된다.
   2. 따라서, 흰 칸에 있는 비숍, 검은 칸에 있는 비숍을 따로 보면 된다. => 5x5 격자를 두번 보는 셈
2. 우선 전체 격자를 스캔하면서 비숍의 위치를 리스트에 넣어준다.
   1. 이 때, x좌표 + y좌표가 짝수라면 흰칸, x좌표 + y좌표가 홀수이면 검은칸 
   2. 비숍의 위치가 검은칸이라면 검은칸 비숍만 저장해두는 리스트에, 흰 칸이라면 흰칸 비숍만 저장해두는 리스트에 따로따로 저장해 둔다.
3. 검은칸일때, 흰칸일때 따로따로 recursion으로 비숍을 하나하나 둬보면서 시뮬레이션 한다.
   1. i번째 비숍을 둘 때, 현재 둔 비숍과 겹치는지(대각선) 확인한다. 
   2. 겹친다면 비숍을 두지 않고 i+1번째 비숍으로 넘억나다.
   3. 겹치지 않는다면 비숍을 두고 i+1번째 비숍으로 넘어가 보고, 비숍을 두지 않을수도 있으므로 두지 않고도 i+1번째 비숍으로 넘어가본다.
4. 검은칸 일때의 최대 비숍의 수, 흰칸 일때의 최대 비숍의 수를 더한 다음 출력한다.

와.. 단순하게 격자를 10x10으로만 보았는데 찾아보니 흰칸, 검은칸을 따로따로 보아야 한다고 함.. 간단하게 소스 몇줄만 바꿔주었을 뿐인데 극적으로 효율이 좋아짐. 10x10에 대해 백트래킹 하는것 보다 5x5에 대해 백트래킹 두번 하는게 훨씬 빠르다는 거에 유의하고 백트래킹을 하려고 할 때 너무 크면 쪼개서 백트래킹 해야된다는걸 배움.

소스 코드

import sys

input = lambda : sys.stdin.readline()

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

bishop = set()
white_bishop_list = [(x, y) for x in range(n) for y in range(n) if matrix[x][y] == 1 and (x+y)%2 == 0]
black_bishop_list = [(x, y) for x in range(n) for y in range(n) if matrix[x][y] == 1 and (x+y)%2 == 1]

save = [0]

def solve(bishoppos, color):
    can_bishop_list = []
    if color == 0:
        can_bishop_list = white_bishop_list
    else:
        can_bishop_list = black_bishop_list
    
    if bishoppos == len(can_bishop_list):
        save[0] = max(save[0], len(bishop))
        return

    current = can_bishop_list[bishoppos]
    can = True
    for x, y in bishop:
        if abs(x-current[0]) == abs(y-current[1]):
            can = False
            break

    if can:
        bishop.add((current[0], current[1]))
        solve(bishoppos+1, color)
        bishop.remove((current[0], current[1]))
    solve(bishoppos+1, color)

answer = 0
# white
solve(0, 0)
answer += save[0]

# black
save[0] = 0
bishop = set()
solve(0, 1)
answer += save[0]

print(answer)

https://www.acmicpc.net/problem/16987

풀이 과정

1. 문제 이해하기가 제일 어려웠음. 즉, 계란을 왼쪽에서 오른쪽으로 한번씩 들어야 함. 또한 전체 계란 중에서 깨지지 않은 계란이 있다면 칠 수 있으며, 손에 든 계란이 깨졌거나 더이상 깨뜨릴 계란이 없다면 한 칸 오른쪽 계란을 들면 됨. 여기서 더이상 깨뜨릴 계란이 없다면, 계속 오른쪽으로 이동하여 결국 종료하게 될 것
2. 재귀함수를 구성한다.
   1. 현재 단계가 마지막 단계라면(맨 오른쪽 계란까지 모두 끝난 상태), 전체 계란을 조사하면서 계란이 몇개 깨졌는지 카운팅 해주어야 함.
   2. 현재 손에 든 계란이 깨져있거나 안깨진 계란이 없다면 바로 현재 계란의 다음 계란으로 이동함.
   3. (2)를 통과하게 된다면, 시뮬레이션 해주어야 함. 칠 수 있는 계란을 한번씩 다 쳐보는 과정. 하나의 계란을 쳐본 다음에는 다시 더해서 원래 계란으로 만들어 주고, 다음 계란을 쳐주어야 함.
3. 정답을 출력한다.

소스 코드

import sys

input = lambda : sys.stdin.readline()

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

def solve(current):
    if current == len(eggs):
        count = 0
        for s, w in eggs:
            if s <= 0:
                count += 1
                
        return count
    # 현재 손에 든 계란 깨짐
    if eggs[current][0] <= 0:
        return solve(current+1)

    # 안깨진 계란이 남아있는지 체크하는 부분
    for i in range(len(eggs)):
        if i == current:
            continue
        if eggs[i][0] > 0:
            break
    else:
        return solve(current+1)
            
    # 시뮬레이션
    answer = 0
    for i in range(len(eggs)):
        if i == current:
            continue
        if eggs[i][0] <= 0:
            continue

        eggs[i][0] -= eggs[current][1]
        eggs[current][0] -= eggs[i][1]
        
        answer = max(answer, solve(current+1))

        # 다음 차례 가려면 기존에 빼주었던거 다시 더해주어야 함.
        eggs[i][0] += eggs[current][1]
        eggs[current][0] += eggs[i][1]
    
    return answer

print(solve(0))

https://www.acmicpc.net/problem/10473

풀이 과정

1. 시작점, 대포 위치, 도착점을 노드로 잡고 걸리는 시간을 행렬로 구해준다.
   • 시작점 -> 0, 대포들 -> (1 ~ N) 도착점 -> N+1
   • [i][j] => 노드 i에서 노드 j까지의 최소 시간
   • 시작점부터 각 노드의 걸리는 시간을 구하는 경우, 대포를 사용할수 없으며 달려가는 케이스밖에 없으므로 [0][j]는 시작점 ~ 도착점 거리를 구한 다음 5로 나누어주면 된다.
   • 이외의 경우에서는 대포를 사용할 수 있으므로
     1. 달려가는 케이스(거리 / 5)
     2. 거리가 50 초과일 때 대포 + 앞으로 달려가기 (2 + (거리-50)/5)
     3. 거리가 50 미만일 때 대포 + 뒤로 달려가기 (2 + (50-거리)/5)
     4. 거리가 50일 때 2
   • 위 네가지 케이스들을 맞추어서 최솟값을 구해서 행렬을 채워주면 된다.
2. 시작점을 0으로 두고, 다익스트라 알고리즘을 사용한다.
   • 현재 최소 거리인 노드를 잡고, 이동 가능한 모든 노드를 이동해 보면서, 거리를 갱신하는 경우 거리 갱신 및 최소 히프에 거리 저장
   • 따라서, 최소 히프를 사용하면 좀 더 빠르게 구현 가능하다.
3. N+1 노드까지의 최소 거리를 출력한다.

일반 다익스트라 알고리즘보다 어려운거 같은데 정답률은 높음.. 뭐지..?

소스 코드

import sys
import heapq
import math

input = lambda : sys.stdin.readline().rstrip()

def calculate_distance(src, dest):
    return math.sqrt((src[0]-dest[0]) ** 2 + (src[1]-dest[1]) ** 2)

myX, myY = map(float, input().split())
targetX, targetY = map(float, input().split())
N = int(input())

points = [list(map(float, input().split())) for _ in range(N)]
points = [[myX, myY]] + points + [[targetX, targetY]]

time_matrix = [[0] * (N+2) for _ in range(N+2)]

for i in range(len(points)):
    for j in range(i+1, len(points)):
        if i == 0:
            time_matrix[i][j] = calculate_distance(points[i], points[j]) / 5
        else:
            distance = calculate_distance(points[i], points[j])
            time_matrix[i][j] = distance / 5
            if distance > 50.0:
                time_matrix[i][j] = min(time_matrix[i][j],
                                        2 + (distance-50) / 5)
            elif distance == 50.0:
                time_matrix[i][j] = 2.0
            else:
                time_matrix[i][j] = min(time_matrix[i][j],
                                        2 + (50-distance) / 5)
        time_matrix[j][i] = time_matrix[i][j]
        
INT_MAX = int(10e9)
distance = [INT_MAX] * (N+2)
distance[0] = 0
heap = [[0, 0]]

while heap:
    time, next_node = heapq.heappop(heap)
    if distance[next_node] != time:
        continue

    for i in range(len(points)):
        if next_node == i:
            continue
        if distance[i] > time + time_matrix[i][next_node]:
            distance[i] = time + time_matrix[i][next_node]
            heapq.heappush(heap, [distance[i], i])

print("%.6f"%(distance[N+1]))

https://www.acmicpc.net/problem/10775

풀이 과정

1. Union-find 알고리즘을 응용하는 문제이다.
   • find(i)가 의미하는게 게이트 번호가 i일 때 넣을 게이트의 다음 위치라고 보면 된다.
2. 입력받은 게이트의 부모 노드를 찾고(find), 부모노드와 부모노드 - 1 노드를 union 해준다.
   • 부모 노드에는 비행기를 넣었으므로 다음 위치는 (부모노드-1)의 부모노드이기 때문이다.
   • 이 때, Union 연산을 할 때, i 이하의 게이트를 찾아야 하므로 두 점 중에서 큰 번호의 부모를 수정해야 한다.
3. 부모 노드를 찾았을 때, 부모 노드가 0이라면 어느 게이트에도 도킹할 수 없는 것이므로 루프를 중지한다.
4. 결괏값을 출력시켜 준다.

소스 코드

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10**5)

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

G = int(input().rstrip())
P = int(input().rstrip())
parent = [i for i in range(G+1)]
answer = 0

for i in range(P):
    ap = int(input().rstrip())
    where = find(parent, ap)
    if where == 0:
        break
    union(parent, where, where-1)
    answer += 1

print(answer)

https://www.acmicpc.net/problem/16434

풀이 과정

1. 최소 생명력을 1, 최대 생명력을 넉넉하게 10^16정도 잡아두고 최소를 찾는 것이므로 크다고 문제가 되는건 아니니까 이진 탐색을 진행한다. 
2. 범위의 중간값을 기준으로, 던전을 끝까지 클리어할 수 있는지 시뮬레이션 해본다.
   1. 몬스터인 경우, 몬스터의 체력 // 현재 공격력만큼 전투를 해야 한다.
   2. 따라서 몬스터의 공격력 x (몬스터의 체력 // 현재 공격력) 만큼 현재 hp에서 빼주면 된다. 단, 이 때 나누어 떨어지는 경우는 전투가 딱 맞춰서 끝나는 경우이므로 몬스터의 공격력 x (몬스터의 체력 // 현재 공격력 - 1)을 빼준다.
   3. 포션인 경우는 공격력은 그냥 올려주고, 체력의 경우 최대 체력까지만 올라갈 수 있도록 처리해 준다.
3. 던전의 끝까지 클리어할 수 있다면 최대 체력의 최솟값을 구해야 하므로 정답 저장 후 왼쪽 구간을 진행하고, 클리어할수 없다면 최대 체력을 올려야 하므로 오른쪽 구간을 진행한다.
4. 정답을 출력한다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

N, Hatk = map(int, input().split())

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

left = 1
right = int(10e16)
answer = 0
while left <= right:
    mid = (left + right) // 2
    current_HP = mid
    current_ATK = Hatk
    status = True
    for dungeon in dungeons:
        t, a, h = dungeon
        if t == 1:
            step = h // current_ATK
            if h % current_ATK == 0:
                step -= 1
            current_HP -= a * step
            if current_HP <= 0:
                status = False
                break
        elif t == 2:
            current_HP = min(current_HP+h, mid)
            current_ATK = current_ATK + a
        
    if status:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer)

https://www.acmicpc.net/problem/1774

풀이 과정

1. 입력받은 우주신들의 좌표를 사용하여 서로 다른 우주신들 사이의 거리를 모두 구해서 최소히프에 넣어준다.
   • (1->2, 1->3, ..., N-1->N)
   • 최소 히프에는 거리 기준으로 최소 히프에 넣을거기 때문에 (거리, 시작점, 끝점) 순으로 넣어준다. 
2. 미리 연결된 우주신들에 대해서는 Union 연산을 미리 해준다.
3. 이후 히프에서 하나씩 꺼내면서 연결된 점이 같은 집합에 속해있는지 검사한다.(find) 속해있지 않다면 해당 간선을 사용해야 하므로 union 연산을 해주고, 거리는 따로 더해둔다.
4. 따로 더해둔 거리를 출력시켜 준다.

같은 kruskal 알고리즘을 사용하더라도 응용해야 되는 문제들이 풀기가 좀 어렵다. 이번 문제에서는 간선 정보가 주어지지 않고, 푸는 사람이 직접 만들어야 했기 때문에 더 그랬던 것 같음.

소스 코드

import sys
import heapq
import math

input = lambda: sys.stdin.readline().rstrip()

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

def union(parent, a, b):
    pa = find(parent, a)
    pb = find(parent, b)

    if parent[pa] != parent[pb]:
        parent[pa] = parent[pb]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])

    return parent[a]

pos = [[0, 0]]

parent = [i for i in range(N+1)]

for _ in range(1, N+1):
    x, y = map(int, input().split())
    pos.append([x, y])

for _ in range(M):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)

heap = []

for i in range(1, N+1):
    for j in range(1, i):
        distance = math.sqrt((pos[i][0] - pos[j][0]) ** 2 + (pos[i][1] - pos[j][1]) ** 2)
        heapq.heappush(heap, [distance, i, j])

answer = 0
while heap:
    dist, i, j = heapq.heappop(heap)
    if find(parent, i) != find(parent, j):
        answer += dist
        union(parent, i, j)
    else:
        continue

print("%.2f"%answer)

https://www.acmicpc.net/problem/2225

풀이 과정

1. 1차원 DP로도 풀 수 있겠지만, 2차원 DP로 풀이하는 편이 훨씬 직관적이고 보기 편하다.
2. DP[i][j]를 j개의 숫자를 써서 i를 만드는 경우의 수라고 할 때,
   1. DP[i][j]의 값은 DP[i][j-1]~DP[0][j-1]의 합과 같다.
   2. DP[i][j-1]의 케이스에서 숫자 0을 사이사이에 더해주면 되고, 비슷하게 DP[i-1][j-1]의 경우는 숫자 1, ... 숫자 i를 더해줄 때는 DP[0][j-1]이므로 (1)과 같다.
   3. DP[i][j]를 구하고 나서 나머지 연산을 같이 해주어야 속도가 빨라진다.
3. DP[N][M]을 출력시켜준다.

DP 점화식 고민할 때 너무 문제를 크게 잡고 고민하지 말고 작게 고민해야 함.. ㅜㅜ

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
dp = [[0] * (M+1) for i in range(N+1)]

for i in range(M+1):
    dp[0][i] = 1

for i in range(1, N+1):
    for j in range(1, M+1):
        for k in range(0, i+1):
            dp[i][j] += dp[k][j-1]
        dp[i][j] = dp[i][j] % 1000000000

print(dp[N][M])