사용자 도구

사이트 도구


ps:problems:boj:17143

낚시왕

ps
링크acmicpc.net/…
출처BOJ
문제 번호17143
문제명낚시왕
레벨골드 2
분류

구현

시간복잡도O(r*c^2)
인풋사이즈r<=100, c<=100
사용한 언어Python
제출기록31244KB / 528ms
최고기록528ms
해결날짜2021/11/12

풀이

  • 그냥 시키는 대로 구현하면 되는 문제. 발상은 어려울게 없지만 구현이 번거롭다.
  • 일단 귀찮은 부분은 상어의 현재위치, 이동 방향, 속도가 주어져있을때 다음 위치와 방향를 구하는 로직. 일단 이동방향과 속도로 들어오는 입력을 그냥 dx와 dy로 바꿔서 저장해두면 계산이 조금 간단해진다. 다음으로는 모서리에 부딪히면 180도로 방향을 바꿔서 이동하는 처리가 귀찮은데.. 생각해보면 좌우로 이동하는 경우 주기가 (C-1)*2 만큼이라는 것을 알수 있다. 그래서 일단 dx만큼 더해주고, (C-1)*2 로 나눈 나머지를 구한다음, 그 값이 C이하면 오른쪽을 보고 있는 방향, C보다 크면 반사된 위치로 위치를 구하고, 왼쪽을 보고 있는 방향으로 업데이트 해주면 된다.
  • 사람의 위치가 c가 되었을때 c행에서 가장 땅에 가까운 상어를 찾는 것을 루프로 처리하는 대신에, 이전 단계에서 상어들의 위치를 업데이트해줄때 미리 계산해두는 방법이 코드를 조금 더 간단하게 해준다
  • 낚시왕이 C칸 이동하는 동안 매번 R*C개의 칸을 모두 확인해서 각각의 상어를 O(1)에 업데이트하므로, 전체 시간 복잡도는 O(R*C*C)이다.

코드

"""Solution code for "BOJ 17143. 낚시왕".

- Problem link: https://www.acmicpc.net/problem/17143
- Solution link: http://www.teferi.net/ps/problems/boj/17143

Tags: [Implementation]
"""

import sys

INF = float('inf')
UP, DOWN, RIGHT, LEFT = 1, 2, 3, 4


def main():
    R, C, M = [int(x) for x in sys.stdin.readline().split()]
    sharks = [[None] * C for _ in range(R)]
    min_r = INF
    for _ in range(M):
        r, c, s, d, z = [int(x) for x in sys.stdin.readline().split()]
        dr = dc = 0
        if d in (UP, DOWN):
            dr = -s if d == UP else s
        else:
            dc = -s if d == LEFT else s
        sharks[r - 1][c - 1] = (dr, dc, z)
        if c - 1 == 0:
            min_r = min(r - 1, min_r)

    answer = 0
    r_round, c_round = (R - 1) * 2, (C - 1) * 2
    for col in range(C):
        if min_r != INF:
            answer += sharks[min_r][col][2]
            sharks[min_r][col] = None

        prev_sharks, sharks = sharks, [[None] * C for _ in range(R)]
        min_r = INF
        for r, prev_sharks_r in enumerate(prev_sharks):
            for c, prev_shark in enumerate(prev_sharks_r):
                if not prev_shark:
                    continue
                dr, dc, size = prev_shark
                nr, nc = (r + dr) % r_round, (c + dc) % c_round
                if nr >= R:
                    nr, dr = r_round - nr, -dr
                elif nc >= C:
                    nc, dc = c_round - nc, -dc
                if not (shark := sharks[nr][nc]) or shark[2] < size:
                    sharks[nr][nc] = (dr, dc, size)
                if nc == col + 1:
                    min_r = min(nr, min_r)

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N B J F T
 
ps/problems/boj/17143.txt · 마지막으로 수정됨: 2021/11/15 13:40 저자 teferi