ICPC Practice #2. 2015 Pacific Northwest Regional (Div 2.)
(문제 세트) https://www.acmicpc.net/category/809
#1과 동일하게 3시간 돌렸습니다.
http://acmicpc-pacnw.org/ProblemSet/2015/index2.html
1위 노려봐도 되나요 ?
[문제 풀이]
Div 2. M번. Magic Trick
https://www.acmicpc.net/problem/11605
11605번: Magic Trick
The first line of input contains a single positive integer n (1 ≤ n ≤ 10). Each of the next n lines consists of an operation, followed by an operand. The operation is one of the strings ADD, SUBTRACT, MULTIPLY, or DIVIDE. Operands are positive integ
www.acmicpc.net
1부터 100까지의 수 중 $N$개의 연산을 진행했을 때, 연산이 불가능한 수의 개수를 구해야 합니다. 계산 도중 음수나 분수가 나올 경우 연산이 불가능하다고 보고 있으므로, 이에 유의해주면 됩니다.
제 풀이는 큐(Queue)를 이용합니다. 큐에 1부터 100까지의 수를 넣고, 다음의 과정을 $N$번 반복합니다.
- 현재 큐의 크기를 알아둡니다.
- 큐에서 수를 뽑고, 연산을 진행합니다.
- SUBTRACT 연산에 의해 수가 음수가 되거나, DIVIDE 연산에 의해 분수가 나올 경우(즉, 나누었을 때 나머지가 0이 되지 않는 경우), 그대로 종료하고, 그렇지 않은 경우엔 계산된 결과를 다시 큐에 넣습니다.
- 2~3을 1.에서 구한 크기만큼 반복합니다.
물론 구현 방법은 다양할 수 있습니다.
Div 2. N번. Egg Drop
https://www.acmicpc.net/problem/11606
11606번: Egg Drop
The first line of input contains two space-separated integers n and k (1 ≤ n ≤ 100, 3 ≤ k ≤ 100), the number of egg drops and the number of floors of the building, respectively. Each of the following n lines contains a floor number and the result o
www.acmicpc.net
첫 번째로, "달걀이 깨질 수 있는 가장 낮은 층"부터 구해봅시다. 어떤 $x$에 대하여 $x$층에서는 달걀이 깨지지 않는다고 합시다. $x$보다 낮은 층에서는 달걀이 (당연히) 깨지지 않고, $x$층보다 높은 층에서는 달걀이 깨질 가능성이 있습니다. 이때 $x < y$인 $y$층에서도 달걀이 깨지지 않는다고 합시다. $x$~$y$층에서도 달걀이 깨지지 않으므로 달걀이 깨질 가능성이 있는 층은 $y+1$층부터입니다. 따라서 첫 번째 답은, 1층부터 $k$층을 차례대로 순회했을 때, BROKEN이 입력으로 들어온 층에 1을 더한 층임을 알 수 있습니다.
두 번째로, "달걀이 깨지지 않는 가장 높은 층"을 구해봅시다. 어떤 $x$에 대하여 $x$층에서는 달걀이 깨진다고 합시다. $x$보다 높은 층에서는 달걀이 (당연히) 깨지고, $x$층보다 낮은 층에서는 달걀이 깨지지 않을 가능성이 있습니다. 이때 $x > y$인 $y$층에서도 달걀이 깨진다고 합시다. $x$~$y$층에서도 달걀이 깨지므로 달걀이 깨지지 않을 가능성이 있는 층은 $y-1$층부터입니다. 따라서 두 번째 답은, $k$층부터 1층을 차례대로 순회했을 때, SAFE가 입력으로 들어온 층에 1을 뺀 층임을 알 수 있습니다.
Div 2. O번. Grid
https://www.acmicpc.net/problem/11607
11607번: Grid
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains two space-separated integers n and m (1≤n,m≤500), indicating the size of the grid. It is guaranteed th
www.acmicpc.net
기본적인 BFS 문제. 문자열로 입력을 받는다면, 각 격자에 대하여 (char형) '0'을 빼주어 다음 격자를 탐색해야 함에 유의해야 합니다.
Div 2. P번. Complexity
https://www.acmicpc.net/problem/11608
11608번: Complexity
Print, on a single line, the minimum number of times you need to use the eraser.
www.acmicpc.net
지우지 않을 글자를 2개 정하고, 문자열을 돌면서 정해진 글자가 아닌 경우 카운트해줍니다. 모든 경우 중 카운트가 가장 작은 수가 답이 됩니다. complexity가 1이 되게끔 하려면, 지우지 않을 글자를 2개 정할 때, 2개의 글자를 모두 같은 글자로 설정하면 됩니다.
Div 2. Q번. Excellence
https://www.acmicpc.net/problem/11597
11597번: Excellence
The World Coding Federation is setting up a huge online programming tournament of teams comprised of pairs of programmers. Judge David is in charge of putting teams together from the Southeastern delegation. Every student must be placed on exactly one team
www.acmicpc.net
(준비 중)
Div 2. R번. Class Time
https://www.acmicpc.net/problem/11609
11609번: Class Time
The first line of input contains an integer n (1 ≤ n ≤ 100), the number of students in Tom’s class. Each of the following n lines contains the name of a single student: first name, followed by a single space, then last name. The first and last name b
www.acmicpc.net
단순 커스텀 정렬. C++ 기준으로, 저는 sort함수에 다음과 같은 비교함수를 넣었습니다.
bool cmp(pair<string, string>& s1, pair<string, string>& s2)
{
if(s1.second != s2.second)
return s1.second < s2.second;
return s1.first < s2.first;
}
Div 2. S번. Surf
https://www.acmicpc.net/problem/11610
11610번: Surf
The first line of input contains a single integer n (1 ≤ n ≤ 300,000), representing the total number of waves for the day. The ith line (1 ≤ i ≤ n) that follows will contain three space separated integers: mi, fi, and wi, (1 ≤ mi, fi, wi ≤ 106)
www.acmicpc.net
우선 다음과 같은 DP식을 생각해봅시다.
- $dp[i]$ = $i$분까지 파도를 탔을 때 얻을 수 있는 Fun points의 최댓값
어떤 파도의 {Minute, Fun points, Wait time} 구성이 {2, 80, 9}라고 하고, $dp[2] = 0$이라고 해봅시다. 이 파도를 타게 된다면, $dp[2 + 9] = 80$이 됨을 알 수 있습니다. 즉 시간 1~200000을 차례대로 순회하면서, 어떤 파도의 {Minute, Fun points, Wait time} 구성이 {$i$, $f$, $w$}라고 하면, $dp[i+w]$를 $dp[i+w]$값과 $dp[i] + f$값을 비교하여 그 중 최댓값으로 갱신할 수 있습니다. 이때 현재까지의 Fun points의 최댓값을 계속 들고다녀야 할 필요가 있으므로, 각 시간을 순회하면서, $dp[i]$에는 지금까지의 $dp[i]$ 값과 현재까지의 최댓값인 $dp[i-1]$ 중 최댓값을 먼저 저장시켜놓아야 합니다.
Div 2. T번. Triangle
https://www.acmicpc.net/problem/11596
11596번: Triangle
The input consists of two lines. The first line contains three space-separated positive integers, indicating the desired side lengths of the first triangle. Similarly, the second line contains three space-separated positive integers, denoting the desired s
www.acmicpc.net
어떤 직사각형을 잘라 두 삼각형으로 만들기 위해서는 직사각형의 한 대각선을 자르는 방법 밖에 없습니다. 이때 만들어진 두 삼각형의 세 변의 길이는 각각 같음을 쉽게 알 수 있습니다. 따라서 우선, 두 삼각형의 세 변의 길이가 각각 같은지를 살핍니다. 다음으로, 이렇게 잘라진 삼각형은 직각삼각형이므로, 피타고라스 정리인 $a^2 + b^2 = c^2$를 만족하는지 확인합니다. 두 조건 중 한 가지라도 만족하지 못하면 NO를 출력해야 합니다.
Div 2. U번. Blur
https://www.acmicpc.net/problem/11611
11611번: Blur
The first line of input contains three space-separated integers w, h, and b (3 ≤ w, h ≤ 100, 0 ≤ b ≤ 9), denoting the width and height of the image, and the number of times to blur the image, respectively. The following h lines of w space-separated
www.acmicpc.net
격자의 모든 점을 3x3격자의 중심으로 보고, 그 점에 3x3격자에 적혀 있는 수의 평균을 넣어야 합니다. 격자를 무한하게 펼칠 필요 없이, 격자의 행을 $N$개, 열을 $M$개라고 할 때, 임시 격자인 $(N+2)$ X $(M+2)$행렬을 준비하여, 원래 격자의 모든 점이 3x3격자를 가질 수 있도록 수를 알맞게 넣어줍니다. (예를 들어, 임시 격자의 (1, 1)에 들어갈 수는 원래 격자의 (N, M)에 있던 수입니다.)
임시 격자를 통해 격자의 수들을 모두 바꿀 수 있도록 합니다. 중요한 점은 Warning에서도 경고하고 있듯이, 실수 자료형을 쓰면 안 된다는 것입니다. 따라서 직접 분수 구조체를 구현해봅시다. 각 격자마다 (분자, 분모) 수를 모두 가지고 있다고 합시다. (초기의 1은 (1, 1)로, 0은 (0, 1)로 표현할 수 있습니다.)
분수의 덧셈은 익히 알고 있는 통분 방법을 그대로 따릅니다. 두 분수를 통분할 때, 분모는 다음과 같이 구할 수 있습니다. 어떤 두 수 $A$, $B$의 최소공배수는 $A$와 $B$를 곱한 수에 $A$와 $B$의 최대공약수를 나누어 구합니다. 분모가 변한만큼 각 분수의 분자에도 동일한 수를 곱해줍니다. 분자를 더한 뒤, 기약분수로 만들어 줍니다. (이때에도 최대공약수를 구해주어 계산합니다.)
평균을 구해야 하므로, 분모에 9를 곱해주고 다시 기약분수로 만들어 줍니다. 기약분수로 만들어 주는 이유는, 어떤 두 분수가 같은 수임에도 표현이 달라 다른 수로 인식하는 것을 막기 위해서입니다.
이를 $b$번 반복합니다.
[업솔빙]
(추후 추가 예정)