내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
낚시왕
ps:problems:boj:17143
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 낚시왕 ====== ===== 풀이 ===== * 그냥 시키는 대로 구현하면 되는 문제. 발상은 어려울게 없지만 구현이 번거롭다. * 일단 귀찮은 부분은 상어의 현재위치, 이동 방향, 속도가 주어져있을때 다음 위치와 방향를 구하는 로직. 일단 이동방향과 속도로 들어오는 입력을 그냥 dx와 dy로 바꿔서 저장해두면 계산이 조금 간단해진다. 다음으로는 모서리에 부딪히면 180도로 방향을 바꿔서 이동하는 처리가 귀찮은데.. 생각해보면 좌우로 이동하는 경우 주기가 (C-1)*2 만큼이라는 것을 알수 있다. 그래서 일단 dx만큼 더해주고, (C-1)*2 로 나눈 나머지를 구한다음, 그 값이 C이하면 오른쪽을 보고 있는 방향, C보다 크면 반사된 위치로 위치를 구하고, 왼쪽을 보고 있는 방향으로 업데이트 해주면 된다. * 사람의 위치가 c가 되었을때 c행에서 가장 땅에 가까운 상어를 찾는 것을 루프로 처리하는 대신에, 이전 단계에서 상어들의 위치를 업데이트해줄때 미리 계산해두는 방법이 코드를 조금 더 간단하게 해준다 * 낚시왕이 C칸 이동하는 동안 매번 R*C개의 칸을 모두 확인해서 각각의 상어를 O(1)에 업데이트하므로, 전체 시간 복잡도는 O(R*C*C)이다. ===== 코드 ===== <dkpr py> """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() </dkpr> {{tag>BOJ ps:problems:boj:골드_2}}
ps/problems/boj/17143.txt
· 마지막으로 수정됨: 2021/11/15 13:40 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로