문제 이해 단계 https://www.acmicpc.net/problem/16926 문제 자체를 NxM 배열이 주어지고 회전 횟수 R이 주어진다. 회전 횟수 R만큼 반시계방향으로 예제로 주어진 패턴처럼 돌리면 된다. 그림을 보면 쉽게 패턴 파악이 가능하기 때문에 따로 설명은 안 하겠다. 문제 접근 단계 이 문제는 배열을 반시계방향으로 회전시키는 것이기 때문에, 단순 구현 문제에 해당하는 것 같다. 문제는 같은 행이나 열에 있는 것은 그냥 오른쪽에 있는 값을 가져오면 되는데, 각 모서리에 있는 값 같은 경우는 가져와야 하는 부분이 각각 다르다. 예를 들어 아래 그림과 같이 왼쪽 위는 오른쪽에서, 오른쪽 위는 아래에서,오른쪽 아래는 왼쪽에서, 왼쪽 아래는 위에서 가져와야 한다. 이 규칙은 안에 있는 사각형에..

문제 이해 단계 https://www.acmicpc.net/problem/15787 입력으로 N개의 열차와 M개의 명령이 주어진다. 각 열차에는 한 줄로 20개의 좌석으로 구성되어 있다. 명령은 총 3마디로 주어지는데, 첫 번째는 명령의 종류 두 번째는 명령을 받을 기차, 세 번째는 좌석을 뜻한다. 명령의 종류는 다음과 같다. 1. 해당 기차의 해당 좌석에 인원 추가 2. 해당 기차의 해당 좌석에 인원 제거 3. 해당 기차 모든 인원 1칸 뒤쪽으로 이동 4. 해당 기차 모든 인원 1칸 앞쪽으로 이동 이러한 명령이 끝났을 때, 좌석의 인원 배열이 중복을 제외하고선 몇 개인지 계산하는 문제 문제 접근 단계 해당 문제에서 중요하게 봐야 하는 점은 각 기차가 모두 20개의 좌석으로 이루어져 있고, 한 줄로 나열..

문제 이해 단계 문제가 이해하기가 어려웠는데 최대한 쉽게 풀어써보겠다. 전체 문자열이 존재하고 하나씩 드러나게 하는데 이걸 전체 단어로 볼 때 사전순으로 가장 빠르게 하는 것이다. 앞에 있는 알파벳이 높을수록 사전순으로 빠르기 때문에 맨 앞부터 높은 알파벳부터 채우는 것이다. 예제 출력 3번을 보면 어느 정도 이해가 된다. 문제 접근 단계 해당 문제에서 포인트가 되는 부분은 총 2가지이다. 1. 다음에 올 문자를 정하는 규칙 2. 그 문자를 적절한 곳에 위치시키는 방법 1번은 문제 조건에서 사전 순으로 빠르게 선택하라고 했기 때문에 빠른 순서대로 선택해야 하기 때문에 중요한 것이고, 2번은 문자가 무조건 뒤에 추가되는 것이 아닌, 사이사이에 들어갈 수도 있기 때문이다. 예를 들어 AIK 다음에 AINK ..

문제 이해 단계 https://www.acmicpc.net/problem/20164 홀수개의 숫자가 입력으로 들어온다. 이때 숫자의 개수에 따라 다음에 규칙에 따른다. 숫자의 개수가 1개 -> 그대로 숫자의 개수 2개 -> 두 수를 더함 숫자의 개수 3개 이상 -> 임의의 지점에서 세 수를 나누어서 더함 위 행위를 숫자의 자릿수가 하나가 남을 때까지 반복한다. 이 과정에서 홀수가 총 몇 번 등장하는지를 세는 것인데, 숫자의 개수가 3개 이상일 때는 임의의 지점에서 나누기 때문에 여러 가지 경우의 수가 생긴다. 그래서 나올 수 있는 홀수의 최댓값과 최솟값을 구하는 문제이다. 문제 접근 단계 해당 문제에서의 핵심은 숫자의 개수가 3개 이상일 때 숫자를 3개의 분할로 나누는 것이다. 이걸 어떤 식으로 나눠야 ..

문제 이해 단계 https://www.acmicpc.net/problem/2615 문제는 그냥 우리가 흔히 알고 있는 오목에 관한 문제이다. 흑돌과 백돌의 배치가 주어졌을 때 현재 상태가 누가 이긴 상태인지, 아니면 승부가 나지 않은 상태이지 판가름하는 문제이다. 이 문제 조건에서 5개 연속을 넘은 6개 연속, 7개 연속은 이긴 것으로 판정하지 않는다. 또한 오목이 발생하는 것은 단 하나이며, 흑돌과 백돌이 동시에 이기는 경우는 발생하지 않는다. 중요한 조건은 출력할 때, 가장 왼쪽에 있는 바둑알의 좌표를 출력하는 것이다. 만약 세로로 일자로 놓여있다면 가장 높이 있는 바둑알의 좌표를 출력한다. 문제 접근 단계 이 문제에서 중요한 것은 어떻게 오목을 판정할 것인가에 대한 문제이다. 오목은 5개의 같은 바..

문제 이해 단계 https://www.acmicpc.net/problem/16926 문제 조건만 보면 무슨 소리인지 전혀 모르겠는데 밑에 첨삭된 그림을 보면 어떤 식으로 배열하라는지 바로 알겠다. 그림처럼 가운데를 중심으로 X자 모양으로 2개의 직선과 + 모양으로 2개의 직선을 그리는 것이다. 그리고 가운데를 중심으로 45도를 단위로 돌렸을 때의 결과를 구하는 문제이다. 문제 접근 단계 해당 문제에서 요구하는 것은 배열을 회전시키는 것이다. 회전시켰다는 것을 확인하기 위해 12시 방향에 있던 5가 3시 방향에 위치하는 등, 어떤 그룹의 이동을 통해 확인한다. 여기서 생각이 든 게, 저 배열들을 확실한 그룹으로 나눌 수 없을까? 아래 그림같이 나누면 n이 아무리 늘어나도 같은 방식으로 포함시키면 되기 때문..

문제 이해 단계 집이 원형으로 배치되어 있고, 한 집을 선택하면 양 옆에 있는 집을 선택할 수 없게 된다. 이러한 조건일 때 얻을 수 있는 가장 많은 숫자 합을 고르는 문제 문제는 엄청나게 간단하다. 문제 접근 단계 일단 배치를 신경 쓰지 말고, 그냥 일반적인 문제처럼 일렬로 집이 있다고 생각해 보자. 그러니까 해당 문제에서 원으로 배치된 것을 어떤 집을 기준으로 일렬로 배치한 것이다. 입력을 주어진 그대로 일렬로 배치해 봤다. 구해야 하는 것은 이 중 최적의 집들을 선택해서 최댓값을 구하는 것이다. 3번 집부터 시작한다고 생각하자. 해당 문제에서 집은 최소 3개라고 했으니 3개부터 살펴본다. 그러니까 현재는 왼쪽에 있는 [2,3,4] 집 밖에 없다고 생각하는 것이다. 집 하나를 고르면 양 옆은 고를 수..

문제 이해 단계 입력으로 2차원 맵과, 지나갈 수 없는 장애물(물 웅덩이)이 0~10개 사이로 주어진다. 이때 집과 학교의 위치는 각각 (1,1) (m, n) 위치에 고정이다. 움직일 수 있는 방법은 오른쪽/아래로 움직이는 방법밖에 없을 때, 최단경로로 집에서 학교로 갈 수 있는 경로의 수를 구하는 문제이다. 문제 접근 단계 일단 출발지에서 목적지까지 경로를 구해야 하고, 맵과 장애물이 주어졌다. 높은 확률로 그래프 탐색 문제로 해결하는 것으로 보인다. 일단 움직일 수 있는 조건을 보면 오른쪽과 아래로밖에 이동하지 못한다. 그리고 찾아야 하는 것은 최단경로의 개수이다. 그렇다면 해당 경로가 최단경로인지 아닌지 어떻게 판단할 수 있을까? 사실 판단할 필요 없다. 왜냐하면 오른쪽과 아래로만 움직일 수 있다면..