본문 바로가기
728x90

알고리즘316

[python] 백준 20057 마법사 상어와 토네이도 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제 해결 토네이도의 움직임을 관찰한 다음 움직이는 모래를 그래프로 이동시켜 그래프를 빠져나가는 모래의 양을 구하는 문제이다. 토네이도의 움직임의 규칙성 부터 찾아야한다. 서, 남, 동, 북 방향으로 순서대로 움직이며 서,남/동,북 으로 바뀔 때 마다 움직이는 칸의 개수가 한 칸 씩 증가한다. 이를 먼저 구현해야한다. 그다음 모래가 흩날리는 영역을 구해야하는데..... 2023. 6. 23.
[python] 백준 20056 마법사 상어와 파이어볼 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제 해결 조건이 한 번에 이해하기 까다로웠다. 이동을 할 때 n행과 1행이 연결되어있어서 n행을 넘어가면 1행으로 텔레포트(?)가 가능하고 1열과 n열이 연결되어있어 n열이 넘어가면 1열로 텔레포트가 가능하다. 그리고 바닥 함수가 기호로 써져있어서 알지 못하면 처음에 이해하기 어려울 수 있다. https://ko.wikipedia.org/wiki/%EB%B.. 2023. 6. 22.
[python] 백준 9328 열쇠 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 해결 주어진 열쇠를 찾고 열쇠에 맞는 문을 열어 최대한 많은 문서를 찾는 문제 움직임을 보면 bfs를 이용하는 것이 편할 것 같다. 하지만 갔던 길을 또 갈 수 있으므로 갔던 길을 체크하는 visited를 성과가 있을 때마다 리셋을 시켜줘야한다. key의 유무를 dictionary를 통해 저장하면 좋을 것 같다. 한 번 얻은 문서는 다시 중복해서 먹을 수 없으므로 문서를 얻었으면 answer += 1을 .. 2023. 6. 22.
[python] 백준 1208 부분수열의 합 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 해결 정수의 최대 개수가 40개이므로 하나씩 계산을 하면 O($40^{40}$) = O(1.2089258e+64)이므로 무조건 시간초과이다. 하지만 연속된 부분수열의 합이 아니고 규칙이 있는 것도 아니기 때문에 하나씩 계산해야 할 수 밖에 없다. 그 결과 수열을 20개씩(절반씩) 잘라서 계산한 후 합이 0이 되는 개수를 더하는 방법을 생각할 수 있다. .. 2023. 6. 22.
728x90