qjatn0120

A. The Ultimate Square code 문제 설명 총 \(N\)개의 직사각형이 있다. \(i\)번째 직사각형은 세로의 길이가 1이고, 가로의 길이가 \([\frac{N}{2}]\)이다. \(N\)개의 직사각형을 회전시키지 않고 만들 수 있는 가장 큰 정사각형의 한 변의 크기를 출력해야 한다. 알고리즘 먼저 \(2N\)개의 직사각형이 있다고 하자. 이 \(2N\)개의 직사각형을 서로 다른 \(N\)개 직사각형 묶음으로 쪼개자. 그렇다면 각 묶음은 \(1 \times 1\) 크기의 직사각형부터 \(1 \times N\) 크기의 직사각형까지 총 \(N\)개의 서로 다른 모양의 직시각형이 있다. 이 \(N\)개의 직사각형을 아래와 같이 계단 모양으로 배열해보자. \(2N\)개의 직사각형으로는 위 계단..

A. ^{-1} code 문제 설명 길이 \(N\)의 순열과 정수 \(X, 1 \le X \le N\)이 주어진다. \(A_i = X\)를 만족하는 \(i\)를 찾아 출력해야 한다. 알고리즘 for문으로 탐색하면서 \(A_i = X\)를 찾아 출력하면 된다. B. Playing Cards Validation code 문제 설명 길이가 2인 문자열이 \(N\)개 주어진다. 이 \(N\)개의 문자열이 카드 묶음에 해당하는 지를 출력해야 한다. 카드 묶음이란 각 문자열이 카드에 해당해야 하고 모든 카드가 서로 달라야 한다. 알고리즘 먼저 각 문자열이 카드에 해당하는 지를 검사하고, 이후 set과 같은 자료구조를 이용해 중복이 있는지를 확인하면 된다. C. Ladder Takahashi code 문제 설명 \(..

A. Indirect Sort code 문제 설명 길이가 \(n\)이고 1부터 \(n\)까지 한 번만 등장하는 배열이 입력으로 주어진다. \(1\le i a_k\)이면 \(a_i\)에 \(a_j\)만큼 더하고, 그렇지 않다면 \(a_j\)와 \(a_k\)를 swap한다. 여러 번의 연산을 통해 배열을 오름차순으로 정렬할 수 있는지 여부를 출력해야 한다. 알고리즘 이 문제는 배열의 첫 번째 원소에 집중하면 빠르게 풀 수 있다. 먼저 배열의 첫 번째 원소가 1이라 가정하자. 그렇다면 \(i = 1\)을 고르면, 두 번째 원소부터 마지막 원소까지 원하는 대로 변경할 수 있어 무조건 바꿀 수 있다. 하지만 첫 번째 ..

A. PassWord code 문제 설명 0부터 9까지의 숫자 중복 허용하여 4개를 사용해 만들 수 있는 비밀번호의 수를 출력해야 한다. 이때, 비밀번호는 서로 다른 숫자를 2개씩 포함해야 하고, 사용하지 않아야 하는 숫자들도 주어진다. 알고리즘 총 10,000가지의 조합을 하나씩 검사해보며 문제의 조건을 만족하는 지 확인해보면 된다. B. Permutation Value code 문제 설명 길이가 \(n\)인 순열 \(a\)에 대하여 이 순열의 값을 연속된 부분 배열이 순열인 부분 배열의 개수로 정의된다. 순열의 값이 최소가 되도록 하는 순열을 출력해야 한다. 알고리즘 먼저 순열의 값은 최소 2라는 것을 쉽게 발견할 수 있다. [1]과 \(a\), 이렇게 2개의 부분 배열이 순열인 경우가 2가지 존재한..

A. Sum code 문제 설명 세 정수 a, b, c가 주어진다. 한 수가 다른 두 수의 합이 될 수 있는지 여부를 출력하면 된다. 알고리즘 if문을 3번 써서 검사하면 된다. B. Increasing code 문제 설명 정수로 이루어진 배열이 주어진다. 이 배열의 원소를 잘 재배치해 strictly increasing을 만족하도록 할 수 있는지를 출력하면 된다. 알고리즘 배열을 정렬한 후에 이웃한 원소 중 같은 게 있는지를 보면 된다. C. Stripes code 문제 설명 8x8의 판에 빨간 가로선과 파란 세로선을 번갈아서 긋는다. 원래 색깔이 있던 칸에 또 칠하면 덮어 씌워진다. 여러 번 색칠한 판의 상태가 주어졌을 때, 마지막으로 칠한 선의 색깔을 출력해야 한다. 알고리즘 빨간 선과 파란 선은 ..

A. Ela Sorting Books code 문제 설명 길이가 \(n\)인 문자열이 주어지고 이를 \(k\)개의 그룹으로 나누고자 한다. \(k\)는 \(n\)의 약수이다. 이제 이 \(k\)개의 그룹의 mex인 알파벳을 구하고 이 알파벳을 나열하여 길이가 \(k\)인 문자열을 만든다. 만들 수 있는 문자열 중 사전순으로 가장 느린 문자열을 출력해야 한다. 알고리즘 먼저, \(k\)개의 그룹을 만들어놓고 여기에 알파벳을 순서대로 할당하는 방식으로 풀어보자. 알파벳 a를 고려해보자. 사전순으로 가장 느리게 만들기 위해서는 a를 맨 앞에 있는 그룹부터 순서대로 넣어줘야 한다. 만약 a의 개수가 \(k\)보다 많다면 남는 a는 아무데나 넣어도 된다. 이는 알파벳 b, c, ... 에 대해서도 성립한다. 따라..

A. Colored Balls: Revisited code 문제 설명 \(N\)종류의 공이 각각 \(cnt_i\)개씩 있다. 총 공의 개수는 홀수 개이다. 여기서 서로 다른 색깔은 가진 두 공을 계속 없애나갈 것이다. 그렇다면 마지막에는 같은 색깔을 가진 공만 남을 것이다. 이때, 남은 공의 색깔로 가능한 색깔 중 하나를 출력하면 된다. 알고리즘 만약 한 색깔의 공이 \(\frac{N + 1}{2}\) 개 이상 있다면, 맨 마지막에는 무조건 그 색깔의 공이 남게 된다. 다른 색깔인 공의 개수를 모두 합쳐도, 그 색깔인 공의 개수보다 더 작기 때문이다. 따라서 \(\frac{N + 1}{2}\)개 이상인 색깔의 공이 존재한다면, 그 색깔을 출력하면 된다. 그 이외의 경우에는 어느 공이든 남게 할 수 있다...

A. Apple 문제 설명 하나의 사과를 X원에 사고, 3개의 사과를 Y원에 살 때 정확히 N개의 사과를 구매하기 위해 필요한 금액을 출력해야 한다. 알고리즘 A 치고는 생각할 부분이 있는 문제였다. 단순 그리디 풀이는 구현이 번거로울 것 같아서 dp 점화식으로 해결하였다. n개의 사과를 사기 위해 필요한 금액을 \(dp[n]\)이라 할 때, \(dp[n] = min(dp[n - 1] + X, dp[n - 3] + Y\)로 계산할 수 있다. B. Explore 문제 설명 총 N개의 방이 있고, i번에서 i+1번 방으로 이동하는 데 \(A_i\)초가 걸린다. \(T\)초가 주어지고, 남은 시간이 0이 되는 일이 없도록 하여 1번에서 N번까지 갈 수 있는지 여부를 출력해야 한다. 이때, M개의 버섯이 있고 ..

2022 PPC 문제를 출제하고 있어서 다른 문제도 볼 겸으로 처음부터 끝까지 풀어보았다. 문제 링크 A. 스키테일 암호 문제 설명 스키테일 암호는 막대에 문자열이 적힌 종이를 말아 암호를 해독하는 기법이다. 문자열의 길이 \(N\)이 주어지고, 맨 처음 글자부터 \(K\)번째 글자마다 읽을 때, 해독 결과를 출력하는 문제이다. 알고리즘 매 \(K\)번째 글자를 출력하면 된다. B. 오델로 문제 설명 \(N \times N\) 크기의 오델로 게임 판이 주어진다. \( (N \le 500) \) 현재 나는 흑돌일 때, 어디에 두어야 가장 많은 백돌을 둘 수 있는지 출력해야 한다. 알고리즘 각 칸마다 흑돌을 두었을 때, 뒤집을 수 있는 백돌의 개수를 구하고 최댓값을 출력하면 된다. 뒤집을 수 있는 백돌의 개..

A. "atcoder".substr() code 문제 설명 입력으로 1이상 7이하의 정수 \(L, R (L < R)\)이 주어진다. 문자열 "atcoder"의 \(L\)번째 글자부터 \(R\)번째 글자까지 출력해야 한다. 알고리즘 \(L\)번째 글자부터 \(R\)번째 글자까지 출력한다. B. Nice Grid code 문제 설명 문제의 그림과 같은 사각형에서 \((R, C)\)칸이 색깔인지 출력해야 한다. 알고리즘 먼저 맨 중앙인 (8, 8)은 하얀 색이고, 여기에서 멀어지면 거리에 따라 색깔이 달라진다. 따라서 행과 열 방향 거리인 \(dr=|8-R|, dc=|8-C|\)를 계산해둔다. 여기서 관찰해보면 dr과 dc 중 큰 값만 중요하다. 즉, \(d = max(dr, dc)\)값에 따라 색깔이 결정된..