나그네

10775번: 공항 문제 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 개인적으로 지문 이해가 어려운 문제였다. 각 비행기는 g번 이하의 숫자의 게이트에 도킹이 가능하고 이미 도킹이 되어있는 곳에는 도킹할 수 없다. 비행기가 도킹을 할 수 없다면 공항은 폐쇄된다. 최대한 많은 비행기를 도킹할 때 가능한 도킹 수를 출력하는 문제다. 유니온 파인드 알고리즘을 사용해서 풀었다. 처음에 비행기가 g번 이하의 게..

27930번: 당신은 운명을 믿나요? 문제 https://www.acmicpc.net/problem/27930 27930번: 당신은 운명을 믿나요? 민지는 11번째 글자까지 읽었을 때 각각 1,3,5,7,9번째의 글자를 제거하고 YONSEI를 찾을 수 있다. www.acmicpc.net 풀이 주어진 문자열을 차례대로 탐색하며 KOREA와 YONSEI 중 먼저 완성되는 문자를 출력하는 문제다. 따라서 주어진 문자열의 각 문자에 대해 KOREA와 YONSEI에 포함된 문자라면 작업을 수행한다. KOREA와 YONSEI가 몇 번째 글자까지 완성되었는지 나타내는 변수 k와 y에 대해 k 또는 y가 (이번 글자가 들어있어야 할 위치 - 1)인 경우 1 증가시켜 줬다. 예를 들어 K는 KOREA의 1번째에만 쓰이므..

27919번: UDPC 파티 문제 https://www.acmicpc.net/problem/27919 27919번: UDPC 파티 첫 번째 줄에 참가자가 투표한 결과 $V$가 주어진다. $V$는 U, D, P, C만 포함하는 문자열이고, 길이는 $0$보다 크고 $100\ 000$을 넘지 않는다. www.acmicpc.net 풀이 U와 C, D와 P를 같은 문자로 생각하고 개수를 센다. D와 P는 둘 다 선정되거나 둘 다 선정되지 않을 수 밖에 없다. U와 C의 수를 UC, D와 P의 수를 DP라고 할 때 U가 선정되기 위해서는 UC의 수가 (DP의 수 + 1) / 2보다 커야한다. 이유는 UC가 2, DP가 4일 때 DP를 2, 2로 나누어도 U가 각각보다 크지 못하므로 U가 선정될 수 없다. 그리고 D..

13975번: 파일 합치기 3 문제 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 풀이 두 개의 파일을 합치는데 드는 비용은 두 파일의 크기의 합이다. 합친 파일을 다른 파일과 또 합칠 수 있고 하나의 파일을 만들기 위해 필요한 비용의 최솟값을 구하는 문제다. 각 파일의 크기가 최대 10,000이고 파일의 수가 최대 1,000,000 이므로 long long 자료형을 사용해야 한다. 작은 두 파일을 합치면 비용이 적게 들고 그 파일을 합칠..

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가 더 가까울 때도 마찬가지. 그러나 틀렸습니다를 받았다. 다음으로 접근한 방..

2812번: 크게 만들기 문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 N자리 숫자에서 숫자 K개를 지워 얻을 수 있는 가장 큰 수를 구하는 문제다. 결과는 N-K자리 숫자가 되는데 앞자리 수가 클수록 큰 수가 될 것은 자명하다. 차례로 순회하며 이번 수보다 앞에 있으면서 작은 수를 지우면 될 것이다. 만약 수를 더 지워야 하면 가장 끝자리 수를 지우면 된다. 스택을 사용해 해결할 수 있고 스택과 같은 형태이면서 값 접근이 용이한 벡터를 사용해 풀었다. 코드 #include using namespace std..

1545번: 안티 팰린드롬 문제 https://www.acmicpc.net/problem/1545 1545번: 안티 팰린드롬 만약 어떤 문자열 P가 있을 때, P[i]와 P[n-i-1] (0 ≤ i

1422번: 숫자의 신 문제 https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net 풀이 K개의 수를 N번 사용해 가장 큰 수를 만드는 문제다. 단, 모든 수는 한 번은 이용해야 한다. 1. K개의 수 정렬 연결했을 때 가장 큰 수를 만들기 위해서 말 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경..

16496번: 큰 수 만들기 문제 https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 풀이 N개의 수를 이어붙여 가장 큰 수를 만들기 위해서 문자 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경우엔 110이 더 크기 때문에 위치가 바뀌지 않는다. 출력 조건이 하나 더 있는데 만약 답이..

1202번: 보석 도둑 문제 https://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 풀이 보석의 무게와 가격이 주어지고 가방에 담을 수 있는 최대 무게가 주어진다. 가방은 최대 1개의 보석만 담을 수 있다. 훔칠 수 있는 보석의 가격의 최댓값을 구하는 문제. 먼저 기본적인 틀은 최대 무게가 가방에 담을 수 있는 보석 중에 가격이 가장 큰 보석을 담는 것이다. 당연히 담을 수 있는 무게가 큰 ..