qjatn0120

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)\)값에 따라 색깔이 결정된..

A. 2-3 Moves code 문제 설명 0번에서 \(n\)번으로 이동하려고 한다. 현재 위치가 \(x\)일 때, \(x+2\), \(x+3\), \(x-2\), \(x-3\)으로 이동할 수 있다. \(n\)번으로 이동하기 위한 최소 이동 횟수를 출력해야 한다. 알고리즘 일단 \(n\)이 1인 경우는 2칸으로 예외 처리를 하였다. 만약 \(n\)이 3의 배수가 아니라면, \(\frac{n}{3}+1\)번 이동해야 한다. 계속 3칸씩 오른쪽으로 이동하다가, \(n\)을 3으로 나눈 나머지가 1이면 2칸씩 2번, 나머지가 2이면 마지막에 2칸 1번을 뛰어야 하기 때문이다. \(n\)이 3의 배수라면 단순히 3칸씩 계속 뛰면 된다. 따라서 뛰어야 하는 횟수는 \( frac{n+2}{3}\)이 된다. \(n\..

A. YES or YES? code 문제 설명 입력으로 들어온 문자열이 대소문자 구분하지 않고 yes인지 확인하는 문제이다. 알고리즘 입력으로 들어온 문자열이 3글자인지 확인하고, 3글자라면 글자가 각각 y, e, s인지 확인한다. B. ICPC Balloons code 문제 설명 문자열로 팀이 어떤 문제를 풀었는지 입력으로 주어진다. (어떤 팀이 풀었는지는 의미가 없으므로 주어지지 않는다.) 문제를 풀면 풍선을 하나 주지만, 처음으로 문제를 풀면 풍선 두 개를 준다. 모든 팀이 받는 총 풍선의 개수를 출력해야 한다. 알고리즘 먼저 문자열의 길이 만큼의 풍선을 주게 된다.그리고 문자열에 있는 알파벳의 종류 개수만큼 추가적으로 풍선을 주게 된다. C. Cypher code 문제 설명 먼저 처음 자물쇠가 어..

A. Round Down the Price code 문제 설명 숫자 \( n\)이 주어진다. \(n\)이하의 \(10^k\)꼴 (\(k\)는 음이 아닌 정수)인 수 중 가장 큰 수를 구한 뒤 \(n-10^k\)를 출력하는 문제이다 알고리즘 단순 구현 문제이다. 반복문을 이용하여 \(n\)이 넘을 때까지 1에서 10씩 곱해나가고, \(n\)을 넘기면 10으로 나눈다. 이 수가 \(n\) 이하의 수 중 최대인 \(10^k\)꼴의 수이다. B. Polycarp Writes a String from Memory code 문제 설명 하루에 최대 3종류의 글자만 적을 수 있다. 문자열 \(s\)가 주어지고 맨 앞글자부터 마지막 글자까지 순서대로 적을 때, \(s\)를 적기 위해 최대 며칠이 걸리는 지 출력해야 한다..

A. When? code 문제 설명 정수 \(0 \le K \le 100 \)이 주어진다. 21:00 으로부터 \(K\)분 지난 시간을 hh:mm 형식으로 출력해야 한다. 알고리즘 60분 이상인 경우 hour에 1을 더해주고, minute를 60만큼 빼준 뒤 출력하면 된다. B. Number Box code 문제 설명 정수 \(1 \le N \le 10\)과 \(N \times N\)짜리 정사각 행렬이 주어진다. 행렬의 각 값은 1이상 9이하이다. 한 점을 정한 뒤, 상하좌우와 대각선까지 총 8방향 중 한 방향을 정해 \(N-1\)칸 움직인다. 만약 범위 바깥으로 나가면 행렬의 반대 방향으로 이동한다. 예를 들어, 맨 왼쪽에서 왼쪽 방향으로 이동하면 맨 오른쪽으로 이동한다. 이와 같이, 총 \(N\)칸을..