목록알고리즘/백준 (65)
개발자 김수진
[문제] https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net [풀이] N*N 격자에 파이어볼 M개가 존재한다. 각 파이어볼은 질량(m), 속력(s), 방향(d)을 가지고 있다. 1. 모든 파이어볼이 d 방향으로 s만큼 움직인다,. 2. 2개 이상의 파이어볼이 있는 칸은 하나의 파이어볼로 합쳐진다. - 합쳐진 파이어볼은 4개의 파이어볼로 나뉘어진다. - 각 파이어볼의 질량은 ( 합쳐진 파이어볼의 질량 합 / 5..
[문제] https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net [풀이] 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 격자별 회전을 처리해주기 위해 rotate api의 인자로 각 격자의 시작 점과 길이를 넘겨주도록 했다. (0,0)을 기준으로 90도 시계 방향 회전하면 (x,y) -> (y, (N-1)-x)로 위치가 변한다. 그런데 해당 문제에서는..
[문제] https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net [풀이] 상어가 구슬 파괴 구슬 이동 구슬 폭발 4개 이상 연속하는 구슬 구슬 이동 구슬 변화 하나의 그룹 => 구슬 A,B ( A는 구슬의 개수 , B는 구슬 번호) 위와 같은 과정이 M번 반복해서 일어난다. 1번부터 5번까지의 각 과정을 api로 분리하여 구현했다. 상어가 구슬을 파괴하는 과정은 destruct_bead , 구슬이 이동하는 과정은 move_bead, ..
[문제] www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net [풀이] 연속된 구간의 부분합을 구하는 문제이므로 투포인터 알고리즘을 사용해서 풀었다. (투포인터 알고리즘 : https://tnwlswkd.tistory.com/44 ) start부터 end까지의 부분합이 S 이상인 경우 구간의 길이를 구하고 start를 한 칸 뒤로 움직여서 구간의 길이를 좁힌다. 이 때 start와 end가 같다면 최소 구간이 되므로 1을 출력하고 끝낸다. 부분합이 ..
[문제] www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net [풀이] 보석의 무게, 가격과 가방의 무게가 주어지고 가방에 담을 수 있는 보석 가격 합의 최댓 값을 구하는 문제 무게를 기준으로 보석과 가방을 오름차순으로 정렬하여 , 가방의 무게를 기준으로 담을 수 있는 보석 무게 중 가격이 가장 높은 것을 선택하는 방식으로 풀었다. 원래는 보석 가격이 가장 높은 것을 선택하기 위해 vector를 사용해 ..
[문제] www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net [풀이] 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 구하는 문제이다. 단 공의 색깔이 같거나 공의 크기가 같다면 잡을 수 없다. 처음에 단순 이중 for문을 사용해서 풀려고 했다. 그러면 시간 복잡도가 O(N^2)이 된다. 하지만 N의 범위가 1 ≤ N ≤ 200,000 이므로 최악의 경우 시간초과가 발생한다. 따라서 다른 방법을 생각했다. 먼저 공의 크기를 ..
[문제] www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 언니의 위치 N, 동생의 위치 K가 입력으로 주어지고 언니가 동생을 찾는데 걸리는 최소 시간을 구하는 문제이다. 숨바꼭질4( www.acmicpc.net/problem/13913) 와 굉장히 유사한 문제이다. BFS를 사용해서 풀었다. 원래 BFS는 방문 체크를 하여 이미 방문한 곳이라면 다시 방문하지 않는다. 하지만 이 문제에서는 순간이동이 있으므로 이미 방..
[문제] www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net [풀이] 추의 무게가 주어지고 추를 사용해서 측정할 수 없는 무게의 최솟값을 구하는 문제이다. 아무리 생각해도 다 더하는 방법 말고는 생각이 안나서 풀이를 봤다. 풀이는 그리디 알고리즘으로 구현했다. 주어진 추의 무게를 오름차순으로 정렬하고 현재까지의 합을 sum이라고 할 때, 더하려는 추의 무게가 sum+2보다 크거나 같다면 sum+1의 무게는 측정할 수 없다. 풀이를 보니 이해는 되지만 문제를 풀면서 어떻게 ..