https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이 유니온 파인드 연습용 문제. 비용이 작은 것을 부모로 연결하는 것이 중요하다. map을 이용해서 부모가 같은 것들을 제외하고 최소 비용을 담아주었다. (연결된 친구 중 가장 작은 비용만 계산하면 되기 때문에 중복 제거가 필요했다.) 그리고 map을 돌면서 비용을 더해주며 k를 초과하는 지 체크해주었다. 다른 글을 찾아보니 다..

https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 풀이 문자열로 표현되어 있지만 사실 경우의 수 문제이다. 최대 1000개의 테스트케이스가 있기 때문에 매번 계산을 하게 되면 시간초과가 나온다. 이전에 계산했던 결과를 저장해야 시간초과가 나지 않아서 DP로 접근했다. cache 배열은 한 조각의 알약의 개수와 반 조각 개수의 최댓값 만큼의 크기로 선언했다. 즉, idx = 한 조각, cnt = 반 조각의 알약 개수다. (앞으로 문제에 맞게 변수 명을 설정하자.)..

https://www.acmicpc.net/problem/20005 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 풀이 최소로 보스몬스터에 접근해야하는 거리를 알아야하기 때문에 BFS 를 사용했다. 전체 map 을 탐색하면서 소문자 알파벳이 있을 경우 BFS 를 돌려주었는데 방문 체크를 하기 위해 visited 배열을 3차원으로 선언했고 보스몬스터에 접근하게 되면 도착시간을 alpha 배열에 넣어주고 BFS 를 종료시켰다. 그리고 HP = N) return fa..

https://www.acmicpc.net/problem/5212 5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net 풀이 언뜻 보면 BFS / DFS 문제 같지만 섬인 부분만 체크하면 되는 조금 생각해야하는 구현 문제다. 그래프 탐색 유형처럼 접근하긴 했는데 map 에서 X 인 부분의 상하좌우를 확인했다. X 의 상하좌우가 map 의 밖에 있거나 바다일 경우 cnt 를 하나씩 늘려주었고 cnt >= 3 일때 X 를 임시로 a 로 바꿔주었다. 지도를 줄이는 부분에서 조금 생각해야할 부분이 있었는데 다시 map 을 탐색하면서 X 인 부분이 있을 때마다 최소 x, y 좌표와 최대 x, y 좌표..

https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 풀이 최대 시간복잡도가 질문 수 200,000 * 문제 수 200,000 이기 때문에 100점을 맞기 위해서는 완전탐색으로는 무리가 있다. 탐색 했던 곳을 재탐색할 필요가 없기 때문에 누적합을 이용했다. 한번의 탐색으로 각 구간별 알파벳의 갯수를 누적합으로 저장했다. 그리고 L ~ R 구간을 구할 때 누적합으로 저장된 R - 1 번째 항에서 L 번..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 분할 정복 문제인걸 바로 알았지만 항상 분할 정복, 재귀는 머리가 아프다. partition 함수를 호출하면 시작부터 끝부분 중에 하나라도 다른 숫자가 있으면 chk 를 false 로 바꿔주었고 false 일 때 4개로 분할해서 재귀를 호출하고 true 일 때 숫자를 저장했다. 괄호 없이 출력하는 건 쉬웠는데 괄호를 어떻게 출력시켜주어야할 지 고민하는 과정이 오래걸렸다. stri..