김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 17143 낚시왕 파이썬(Python)

문제 링크

단순한 빡구현 문제.
난항이 되는 부분은 상어가 벽에 닿으면 방향을 바꾸고 바로 나아간다는 점이다.
직접 케이스를 그려보면서 숫자의 패턴을 찾으면 어떻게든 공식을 구할 수는 있다.
그 외에는 평범한 구현 문제고, 코드가 조금 비효율적이어도 입력이 작아 큰 문제가 안 되는 듯.

#!python

from sys import stdin

# board[i][j][0]은 i, j의 상어의 속도, board[i][j][1]은 방향, board[i][j][2]는 크기
r, c, m = map(int, stdin.readline().split())
board = [[(0, 0, 0) for _ in range(c)] for _ in range(r)]

for _ in range(m):
    rs, cs, s, d, z = map(int, stdin.readline().split())
    board[rs-1][cs-1] = (s, d, z)

ans = 0

# 열의 개수만큼 낚시꾼이 이동
for i in range(c):

    # 그 열에서 상어를 찾으면 낚는다
    for j in range(r):
        if not board[j][i][2]:
            continue
        ans += board[j][i][2]
        board[j][i] = (0, 0, 0)
        break

    # 다음 상어의 위치를 저장할 임시 리스트
    temp = [[(0, 0, 0) for _ in range(c)] for _ in range(r)]

    # 판 전체를 순회
    for k in range(c):
        for j in range(r):
            if not board[j][k][2]:
                continue

            # 각 방향별로 이동 거리를 체크하고 먼저 상어의 방향(d 또는 board[j][k][1])을 수정한다
            # 더 효율적으로 짤 수 있을 듯
            if board[j][k][1] == 1:
                move = (-board[j][k][0], 0)
                if j + move[0] and ((j + move[0]) // (r - 1)) % 2:
                    board[j][k] = (board[j][k][0], 2, board[j][k][2])
            elif board[j][k][1] == 2:
                move = (board[j][k][0], 0)
                if j + move[0] and ((j + move[0] - 1) // (r - 1)) % 2:
                    board[j][k] = (board[j][k][0], 1, board[j][k][2])
            elif board[j][k][1] == 3:
                move = (0, board[j][k][0])
                if k + move[1] and ((k + move[1] - 1) // (c - 1)) % 2:
                    board[j][k] = (board[j][k][0], 4, board[j][k][2])
            else:
                move = (0, -board[j][k][0])
                if k + move[1] and ((k + move[1]) // (c - 1)) % 2:
                    board[j][k] = (board[j][k][0], 3, board[j][k][2])

            # 상어의 위치를 수정한다
            x = min((j + move[0]) % ((r - 1) * 2), ((r - 1) * 2) - (j + move[0]) % ((r - 1) * 2))
            y = min((k + move[1]) % ((c - 1) * 2), ((c - 1) * 2) - (k + move[1]) % ((c - 1) * 2))

            # 내가 더 큰 상어인 경우에만 이동하고 그렇지 않으면 잡아먹힌다
            # 빈 경우 temp[x][y][2] == 0이므로 무조건 이동한다
            if temp[x][y][2] < board[j][k][2]:
                temp[x][y] = board[j][k]

    # board에 temp를 복사한다
    for j in range(r):
        for k in range(c):
            board[j][k] = temp[j][k]

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑