나그네

12014번: 주식 문제 https://www.acmicpc.net/problem/12014 12014번: 주식 입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 www.acmicpc.net 풀이 주가가 올랐을 때만 주식을 사고, 그리고 구매는 하루에 1번만 가능하고 최대 K번만 살 수 있다. 따라서 가장 긴 증가하는 부분 수열의 길이가 K 이상이면 조건을 만족하며 주식을 구매할 수 있다. N의 범위는 10^4이지만 테스트 케이스의 수가 10^2 이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 최대 시간복잡도가 10^10이 되므로 시간복잡도가 O(Nl..

9370번: 미확인 도착지 문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 먼저 가장 큰 접근법은 G-H는 반드시 지나야 하므로 S -> G -> H -> ? 또는 S -> H -> G -> ? 이 최단 경로여야 한다. 따라서 S -> G, S -> H, G -> H, G -> ?, H -> ? 의 최단 거리를 구해야 한다. 즉, 간선 거리는 항상 양수고 몇몇 정점간 거리를 구해야 하므로 다익스트라 알고리즘을 사용했다. 따라서 ..

27868번: On My Way Dorm 문제 https://www.acmicpc.net/problem/27868 27868번: On My Way Dorm 첫 번째 줄에 입력 형식과 같은 방법으로 사무실이 있는 층에서 아인이의 기숙사가 있는 층으로 퇴근하기 위한 커맨드를 출력한다. 가능한 커맨드가 여러 가지일 경우 그중 아무것이나 출력한 www.acmicpc.net 풀이 엘리베이터를 사용한 출근 경로가 주어지고 퇴근 경로를 구하는 문제다. 지문만 보면 어려워 보이지만 출근 경로를 뒤집어서 출력하면 되는 문제다. 지문 난이도와 예제 때문에 헷갈리기 쉽다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NU..

1365번: 꼬인 전깃줄 문제 https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열(LIS)을 구하는 문제다. 전깃줄 문제와 같아 보이나 정렬할 필요가 없는 문제다. 왼쪽 전봇대의 위에서부터 차례대로 어디에 연결되어 있는지 주어지므로 순서대로 LIS를 구하면 된다. N의 범위가 10^5 이므로 시간복잡도가 O(NlogN)인 알고리즘으로 풀어야 시간초과가 안 난다. O(NlogN)으로 LIS를 구하는 방..

11003번: 최솟값 찾기 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 차례대로 수를 입력받아 최소 힙(우선순위 큐)에 추가한다. 가장 작은 숫자가 현재보다 L만큼 이전 범위 안의 수가 아닌 경우, 범위를 벗어나므로 pop 한다. 최솟값이 범위를 만족할 때 top 원소를 출력해 준다. 코드를 줄이고 줄여서 C++ 기준 숏코딩 1등도 했다. (덱을 사용하는 풀이도 있다고 해서 공부한 후에 추가하겠다...

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)인 알고리즘으로 풀 수 없고..