나그네

27724번: 팝핀 소다 문제 https://www.acmicpc.net/problem/27724 27724번: 팝핀 소다 입력의 첫 번째 줄에 대회에 참가하는 선수의 수 $N$, 일어날 수 있는 이변의 수 $M$, 시은이의 탄산 내성 $K$가 공백으로 구분되어 주어진다. 주어지는 모든 수는 정수이다. $(2 \le N \le 262\,144;$ $0 \le www.acmicpc.net 풀이 대회가 토너먼트 형식이므로 항상 자신이 이길 수 있는 상대와 대결해야 최대한으로 승리할 수 있다. 따라서 시은이의 탄산 내성이 K일 때, 시은이가 이길 수 있는 최대 대결의 수는 log2 K번이다. 만약 이변이 있는 경우, 최대한 이길 수 있는 다음 이변의 수만큼 더 이길 수 있다. 따라서 최대 log2 K + M번..

27737번: 버섯 농장 문제 https://www.acmicpc.net/problem/27737 27737번: 버섯 농장 첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다. 버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸 www.acmicpc.net 풀이 버섯 포자를 심을 때마다 개수를 세어준다. DFS로 포자를 심은 부분으로부터 연결되어 심을 수 있는 모든 구간에 포자를 심는다. 포자를 심고 최대 퍼져나갈 수 있는 칸까지 간 다음엔 다시 1부터 시작하고 포자를 심는다. 가능한 모든 공간에 포자를 심은 후에 사용한 포자 수가 0개이거나 사용한 포자 수가 준비한 포자 수보다 많은 경우 버섯 농..

27736번: 찬반투표 문제 https://www.acmicpc.net/problem/27736 27736번: 찬반투표 투표가 통과되었으면 APPROVED, 통과되지 않았으면 REJECTED, 무효 처리되었으면 INVALID를 출력한다. www.acmicpc.net 풀이 찬성, 반대, 무효의 수를 각각 세어 비교하는 문제다. 절반 이상이 기권인 경우 무효이므로 (기권 수 × 2) ≥ N 인 경우 무효다. 무효가 아닌 경우 찬성 수와 반대 수를 비교하여 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int arr[3] = {0}; int n, x; cin >> n; for (i..

5427번: 불 문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 입력 형식과 주어진 횟수의 테스트 케이스를 반복하는 점을 제외하고 4179번 불! 문제와 완전히 똑같은 문제다. 4179번 불! 문제의 풀이도 아래 링크에 있으니 풀이를 참고하면 좋을 것 같다. [4179번 불! 문제] | [4179번 불! 풀이] 각 테스트 케이스마다 다음 과정을 반복한다. 접근법은 상근이와 불에 대해 각각 BFS를 사용하는 것이다. 각각에 대해 1부터 시작해 이동..

2352번: 반도체 설계 문제 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 풀이 전깃줄 문제와 같이 이어진 두 포트가 입력으로 들어오기 때문에 pair로 받아 저장한다. 왼쪽 포트 기준으로 가장 많이 이어야 하기 때문에 입력받은 값들을 정렬한 후 2568번 문제와 같은 알고리즘으로 가장 긴 증가하는 부분 수열(LIS)을 구할 수 있다. N의 범위가 4 × 10^4 이므로 시간복잡도가 O(N^2)인 알고리즘으로 풀 수 없고..

2568번: 전깃줄 - 2 문제 https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 풀이 전깃줄 문제는 이어진 두 지점이 입력으로 들어오기 때문에 pair로 받아 저장한다. A 건물 기준으로 1번부터 이어야 하기 때문에 입력받은 값들을 정렬한다. 그리고 N의 크기가 10^5이기 때문에 시간복잡도가 O(N^2)인 알고리즘으론 시간초과가 나게 된다. 따라서 시간복잡도가 O(NlogN)인 알고리즘을 사용해 14003번 문제와 같이 가장 긴 증가하는 ..

14003번: 가장 긴 증가하는 부분 수열 5 문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이 그리고 N의 크기가 10^6이기 때문에 시간복잡도가 O(N^2)인 알고리즘으론 시간초과가 나게 된다. 따라서 시간복잡도가 O(NlogN)인 알고리즘을 사용해 12015번 문제와 같이 가장 긴 증가하는 부분 수열(LIS)을 구할 수 있다. 그러나 이 알고리즘으론 길이만 구할 수 있고 정확한 수열을 구할 수는 없기..

12738번: 가장 긴 증가하는 부분 수열 3 문제 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이 12015번 가장 긴 증가하는 부분 수열 2 문제와 완전히 같은 알고리즘으로 풀 수 있다. 수열을 이루는 수의 크기에 변화가 있지만 int 범위 안이고 시간복잡도 자체에는 바뀔 부분이 없다. 12015번 해설은 아래 링크를 참고하자. [12015번 가장 긴 증가하는 부분 수열 2 문제] | [12015번 가장 ..

12015번: 가장 긴 증가하는 부분 수열 2 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 LIS 시리즈 문제 중 하나로 N의 범위가 10^5 이상인 문제에선 사용이 불가능한 시간복잡도가 O(N^2) 알고리즘으로는 풀리지 않는 문제다. 이분 탐색을 사용해 시간복잡도가 O(NlogN)인 알고리즘을 사용해 풀었다. 첫 번째 원소는 벡터에 넣어놓고, 다음 원소(편의상 x)부터 비교를 시작한다. 만약 x가 백터의 가장 뒤 원소보다 크다면..

15971번: 두 로봇 문제 https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 풀이 동굴에서 두 점 A, B에서 각자 최소한으로 움직여 간선 하나를 남겨두고 마주할 수 있을 때 통신이 가능하다. 이때 최단 이동 거리를 구하는 문제다. 처음엔 bfs로 A에서 B까지 도달한 다음 B에서 다시 bfs를 시작해 최단 경로 위에서 B의 이동 거리와 B가 이제 갈 곳까지의 A의 이동 거리의 합이 최소인 것을 찾아줬으나 틀렸습니다를 받았다. 친구에게..