봉황대 in CS

문제 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net A와 B로만 이루어진 두 문자열 S와 T가 주어진다. 다음의 두 규칙으로 S를 T로 바꿀 수 있는지를 알아내는 것이 문제이다. 규칙 1. 문자열 뒤에 A 추가 규칙 2. 문자열 뒤에 B 추가 → 문자열 뒤집기 풀이 S를 T로 바꿀 수 있는지를 알아내는 것보다 T를 S로 되돌릴 수 있는지를 보는 것이 더 편하다. 우선, 여러 가지 시도를 해봤을 때 문자열의 맨 앞에 'A', 맨 뒤에 'B'가 오는 경우는 없다는 것을 발..

문제 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 세 수 x, y, z에 대하여 x+y>z, x+z>y, y+z>x의 관계를 만족할 경우, 세 수는 삼각관계에 있다고 한다. 즉, 세 수 중 가장 큰 수를 z라고 할 경우 x+y>z를 만족하면 삼각관계인 것이다. 길이가 N인 수열 B(b[0], b[1], ... , b[n-1])에서 모든 b[i], b[j], b[k]가 삼각관계에 있다면 이 수열은 삼각 수열이라고 한다. (i, j, k..

문제 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 시계 방향으로 돌고 있다. 그림 상 1번 칸이 있는 위치가 로봇을 올리는 위치, N번 칸이 있는 위치가 로봇을 내리는 위치이다. 로봇이 내리는 위치에 도달하면 바로 즉시 컨베이어 벨트에서 내린다. 칸마다 내구도가 정해져 있으며, 로봇이 올라가는 순간 1만큼 감소한다. 컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기는 과정에서 아래의 일들이 순서대로 일어난다. 벨트가 각 칸 위에 있..

문제 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 2^N × 2^N 크기의 격자로 나누어진 얼음판이 주어진다. 파이어스톰 단계 L을 시전하면 1. 격자를 2^L × 2^L 크기의 부분 격자로 나눈다. 2. 모든 부분 격자를 시계 방향으로 90도 회전한다. 3. 얼음이 3개 미만으로 인접해있는 칸은 얼음의 양이 1씩 줄어든다. 파이어스톰을 총 Q번 시전하고 난 후, (1) 남아있는 얼음의 합과 (2) 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구하는 것이 문제이다. (덩어리 ..

문제 5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net 지도를 입력받아 인접한 세 칸 이상이 바다인 땅을 없애서 지도를 출력하면 되는 문제이다. 땅은 'X', 바다는 '.'으로 표시하며, 지도의 범위를 벗어나는 칸은 모두 바다이다. 땅이 적어지기 때문에 지도의 크기도 함께 작아져야 하는 것을 유의해야 한다. 풀이 풀이를 위해 생각해야 하는 것은 2가지, 없어져야 하는 땅을 찾는 방법과 지도의 크기를 줄이는 방법이었다. 1. 없어져야 할 땅 찾기 지도 한 칸마다 탐색, 현재 보는 칸이 땅('X')일 경우 상하좌우로 확인한다. 만약 지도의 범위를 벗어나는 곳이라면 count + 1, 벗어나지..

문제 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 토네이도 이동 방향 토네이도가 x에서 y로 이동 시, y에 있던 모든 모래가 해당 비율만큼 이동한다. (소수점 아래는 버림) 비율이 적혀있는 칸으로 이동하지 않은 남은 모래는 전부 𝛼로 이동한다. 토네이도가 다른 방향으로 이동하는 경우, 위의 비율을 해당 방향으로 회전하면 된다. 토네이도가 (1, 1)까지 이동한 뒤 소멸되었을 때 격자 밖으로 나간 모래의 양을 구하는 것이 문제이다. 풀이 핵심으로 고려해야 했던 것은 토네이도 ..

문제 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 고이는 빗물의 총량 구하기 풀이 1. 가장 왼쪽 블록부터 시작 2. 맨 위쪽 블록부터 맨 아래쪽 블록까지 아래의 수행을 차례대로 진행한다. 2-1. 현재 보고 있는 위치보다 높거나 높이가 같은 블록을 마주쳤을 때, 두 블록 사이에 들어가 있는 공간 개수만큼 고인 물을 저장하는 변수에 더한다. 2-2. 만약 블록을 마주치지 않았다면 두 블록 사이에 고인 물이 없다는 것이므로 더하지 않는다. 3-1. 한 열에 대하여 해당 수행을 완료했을 때, ..

문제 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net K(K>1)세대 드래곤 커브 = K-1세대 드래곤 커브를 끝 점 기준 90도 시계 방향으로 회전 → 그 끝 점에 붙인 것 풀이 첫번째 풀이 드래곤 커브로 그려진 선분을 역순으로 추적하여 '시계 방향 90도 회전 → 끝 점에 붙이기'를 반복하는 것을 통해 직접 좌표들을 계산했다. 선분의 방향마다 그 다음으로 찍혀야 하는 점의 위치를 고려해주어야 하기 때문에 해당 방향 벡터가 시계 방향으로 90도 회전하면 어느 방향 벡터로 바뀌는지에 ..