나그네

29767번: 점수를 최대로 문제 https://www.acmicpc.net/problem/29767 29767번: 점수를 최대로 단대소프트고에는 교실 $N$개가 있다. 교실은 $1$번부터 $N$번까지 $1, 2, \ldots, N$ 순서로 연달아 있다. 학교 밖에는 $K$명의 학생들이 있다. $K$명의 학생은 학교에 들어가기 전 학생마다 목적지 교실 www.acmicpc.net 풀이 목적지 i번 교실에 도착하면 1~i번 방의 점수를 얻습니다. 즉, 누적합 배열로 i번 교실을 목표로 했을 시 얻는 점수를 저장합니다. K명의 학생들은 서로 다른 목적지를 가지므로 누적합 배열을 내림차순 정렬하고 앞에서부터 K개 원소의 합을 출력하면 됩니다. 코드 #include using namespace std; #def..

29158번: 큰 수 만들기 게임 문제 https://www.acmicpc.net/problem/29158 29158번: 큰 수 만들기 게임 성현이와 지훈이는 큰 수 만들기 게임을 하고 있다. 성현이는 양의 정수 $N$이 적힌 카드 $1$장이 들어 있는 주머니를 들고 있다. 지훈이는 성현이의 카드를 몰래 본 다음 성현이의 카드에 적힌 $N$ www.acmicpc.net 풀이 큰 수를 만드는 테크닉은 16496 - 큰 수 만들기 문제와 동일하다. 각각의 수를 문자열로 a = "1", b = "2"인 경우 ab = "12" ba = "21"로 더 큰 수를 만들 수 있는 것은 ba다. 이 정렬 조건으로 수를 정렬한 다음 차례대로 나열하면 된다. 먼저 동작 1과 동작 2가 있는데, 동작 1은 2 이상의 K로 2..

29160번: 나의 FIFA 팀 가치는? 문제 https://www.acmicpc.net/problem/29160 29160번: 나의 FIFA 팀 가치는? 첫 번째 줄에 선수의 수 $N$과 $K$가 공백으로 구분되어 주어진다. $(0\leq N\leq 1\,000\,000;$ $1\leq K\leq 50\,000)$ 두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $i$번째 선수의 포지션 $P_{i}$, 선수 가치 $W_{i}$가 www.acmicpc.net 풀이 항상 가치가 가장 높은 선수를 선발하는 과정을 반복하기 때문에 우선순위 큐(최대 힙)를 사용한다. 11개의 포지션 번호별로 선수를 저장할 수 있는 우선순위 큐 배열을 만든다. 각각의 포지션 번호별로 비어있는 우선순위 큐를 제외하고 한 명씩 선수를..

29155번: 개발자 지망생 구름이의 취업 뽀개기 문제 https://www.acmicpc.net/problem/29155 29155번: 개발자 지망생 구름이의 취업 뽀개기 난이도 $1$에서 $1$분, $4$분, $4$분 순서로, 난이도 $2$에서 $5$분, 난이도 $3$에서 $20$분, 난이도 $4$에서 $40$분, 난이도 $5$에서 $100$분 순서대로 풀면 $1+3+4+0+4+60+5+60+20+60+40+60+100=417$분이 걸린다. www.acmicpc.net 풀이 각 난이도 별로 문제를 푸는 데 걸리는 시간을 저장하고 오름차순으로 정렬한다. 각 난이도별로 풀어야하는 문제의 수만큼 앞에서부터 고르면 된다. 이 문제에서는 문제를 푸는 데 필요한 시간을 최소화하고 휴식시간도 최소화해야한다. 휴식..

28445번: 알록달록 앵무새 문제 https://www.acmicpc.net/problem/28445 28445번: 알록달록 앵무새 재현이가 키우는 앵무새 포포와 레몬이는 그동안 새끼들을 참 많이도 낳았다. 그렇게 태어난 앵무새들을 관찰하며 재현이는 앵무새들의 색에 간단한 규칙이 있다는 것을 발견했다. 그것은 바로 www.acmicpc.net 풀이 색 4가지를 입력받고 가능한 조합을 출력하는 문제다. 2중 for문으로 가능한 조합을 출력했다. 중복처리 및 정렬은 set 자료구조를 사용했다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); set s; for (int i = 0; i < 4; i++) { ..

13274번: 수열 문제 https://www.acmicpc.net/problem/13274 13274번: 수열 지훈이는 수열을 좋아한다. 지금 지훈이는 size 가 N 인 수열을 가지고 놀고 있다. 지훈이는 K 개의 쿼리에 따라 수열을 변화시킬 것인데, 쿼리의 형식 및 작업 과정은 다음과 같다. L R X : 수열을 www.acmicpc.net 풀이 단순한 구현 문제다. 하지만 정렬을 매번 하게 되면 시간초과가 난다! 따라서 정렬을 최소한으로 해야 한다. 그래서 STL sort 함수의 시간복잡도도 찾아보고,, 최악일 때도 O(N log N)인 머지 소트로 해도 안되더라.. 결국 찾은 해결법은 L, R, X를 입력받았을 때 이미 수열은 정렬되어 있다. 그리고 L부터 R까지 X를 더했을 때, 이를 제외한 ..

2887번: 행성 터널 문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 최소 스패닝 트리(MST)를 구현하기 위해 프림 알고리즘을 사용했다. 각 정점의 3차원 좌표가 주어지고 각 정점 간 실제 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 하지만 모든 정점 사이의 |xA-xB|, |yA-yB|, |zA-zB|를 구하게 되면 N^2의 공간복잡도를 가지게 되어 메모리초과가 난다. 따라..

16940번: BFS 스페셜 문제 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 풀이 스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. BFS의 결과가 가능한지 구하는 문제다. BFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 order 배열을 만들고 먼저 방문해야 하는 정점과 연결된 간선이 앞으로 오도록 간선들을 재정렬 한다. 그리고 BFS를 진행하며 탐색 경로를 구한다. 이 경로가 ..

16964번: DFS 스페셜 문제 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 풀이 스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. DFS의 결과가 가능한지 구하는 문제다. DFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 orde..

4716번: 풍선 문제 https://www.acmicpc.net/problem/4716 4716번: 풍선 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 다음 N개 www.acmicpc.net 풀이 각 팀에 필요한 풍선의 개수와 창고 A, B까지의 거리가 주어지면, 가장 효율적으로 창고에서 꺼내서 전달할 때 이동 거리를 구하는 문제다. 처음엔 각 팀이 주어질 때마다 A가 더 가까우면 A에서 양만큼 꺼내주고 충분하지 않으면 B에서 더 꺼내주도록 했다. 반대로 B가 더 가까울 때도 마찬가지. 그러나 틀렸습니다를 받았다. 다음으로 접근한 방..