문제 이해 단계 https://www.acmicpc.net/problem/21608 자리를 정하는 학생의 번호와 그 학생이 원하는 4명의 학생 번호가 한 줄씩 입력으로 들어온다. 입력 순서가 자리를 정하는 순서이다. 여기서 자리를 정하는 것은 3가지 우선순위가 존재한다. 1. 빈칸 중 자기가 원하는 학생들과 제일 많이 인접한 곳에 위치한다. 2. 1번 조건이 여러 개라면 그중에서 주위에 빈자리가 많은 곳에 위치한다. 3. 1,2번 조건이 여러 개면 작은 행, 작은 열로 자리를 앉는다. 여기서 "인접"이란 말은, 자신의 상하좌우 한 칸에 있으면 인접한 것이다. 이렇게 모두 자리를 앉고, 주위에 자신이 원하는 사람이 얼마나 앉았느냐에 따라 점수를 정한다. 0명 = 0점 1명 = 1점 2명 = 10점 3명 =..

문제 이해 단계 https://www.acmicpc.net/problem/22859 상당히 문제가 길고 조건이 많은 문제라 필요한 조건만 밑에 적어보자. HTML 문법 형식으로 줄 바꿈 없이 한 줄로 입력이 들어온다. 핵심이 되는 태그는 이다. 1. 모든 태그와 문자열은 ~ 사이에서 벌어져야 한다. 2. 안에 공백은 존재하지 않는다. 그러니까 이런 식으로 주어지진 않는다는 소리이다. 해당 조건이 주어질 때, 해 당 출력 형식으로 정확히 출력하는 문제이다. 문제 접근 단계 이 문제는 딱 봐도 구현문제다. 그냥 대놓고 구현해 볼 테 면 해봐라 이런 식인 것 같다. 구현해야 할 부분이 많을 것 같아서 함수를 잘 나눠서 설정해둬야 할 것 같다. 일단 필요한 기능을 살펴보자. 최우선적으로 (1) 들어온 문자열을 ..

문제 이해 단계 https://www.acmicpc.net/problem/22856 이진트리에서 왼쪽노드 -> 자기 -> 오른쪽 노드 순으로 방문하는걸 중위 순회라고 한다. 그래서 원래 중위 순회는 제일 왼쪽 노드에서부터 출발하는데, 여기 문제에선 조금 다르다. 해당 문제에서는 무조건 루트 노드인 1에서 출발한다고 가정하고 이동을 거쳐 중위순회를 흉내 내는 것이다. 이때 움직였던 모든 이동 횟수를 구하는 문제 문제 접근 단계 필요한 정보 찾기 일단 노드 1개의 관점에서 바라보자. 각 노드의 관점에서 몇 가지의 정보가 있을까? 총 4개가 있다. 해당 노드의 번호, 왼쪽 자식 노드의 번호, 오른쪽 자식 노드의 번호, 부모 노드의 번호 그리고 중위순회를 할 때 필요한 정보를 생각해 보자. 중위 순회를 할 때는..

문제 이해 단계 재료의 개수 N개가 주어지고 각 재료마다의 쓴맛과 단맛 정보가 주어진다. 쓴맛은 쓴맛끼리 곱연산을 하고 단맛은 단맛끼리 합연산을 해서 (총 쓴맛 - 총 단맛) 해서 최대한 절댓값이 작은 수를 구하는 문제. 문제 접근 단계 일단 문제 조건에서 봐야 할 점은 재료 N이 최대 10개까지만 있다는 점이다. 10개밖에 안되기 때문에 브루트포스가 가능하고, 시간적인 부담이 적다는 것을 알 수 있다. 우선 구해야 하는 것이 뭔지부터 살펴보자. 구하자고 하는 것은 연산의 결과인데, 크게 보면 N개의 재료 중에서 몇 가지를 골라서 그 안에 값을 계산하는 것이다. 여기서 중요한 점은 몇 가지라는 점, 1개가 될 수도 있고 2개가 될 수도 있고 전부가 될 수도 있는 것이다. 그래서 뭔가 공식을 세우거나, 재..

문제 이해 단계 https://www.acmicpc.net/problem/20207 문제가 헷갈리게 적혀있어서 풀면서 문제를 이해하였다. 이런 문제는 좀 예시를 명확히 줬으면 좋겠다. N개의 (시작일자, 종료일자)로 이루어진 블록이 들어오는데 이는 1 ~ 365 사이의 숫자로 이루어져 있다. 이를 열이 365까지 있는 2차원 맵에 1부터 채우는데 블록의 배열은 다음과 같은 규칙을 가진다. 1. 최대한 위쪽부터 채운다. 2. 각기 다른 블록의 시작과 끝이 연속(4,5,6) 이렇게 된다면 무조건 같은 라인(열)에 둔다. 3. 시작일이 같은 경우 긴 것부터 먼저 배열한다. 그리고 우리가 해야 하는 것은 코팅지의 길이를 정하는 것인데, 코팅지는 블록 전체를 감싸는 직사각형으로 만드는 것이다. 근데 이걸 또 최소..

문제 이해 단계 문제는 우리가 익히 아는 스도쿠 규칙과 다를 것이 없다. 9x9 스도쿠가 주어지고 빈칸은 0으로 주어진다. 이러한 입력이 주어졌을 때 빈칸을 채워 스도쿠를 완성시키는 문제이다. 여기서 스도쿠를 완성시킬 수 없는 경우는 존재하지 않는다. 문제 접근 단계 해당 문제에서의 특징은 맵(스도쿠)의 크기가 9x9로 고정되어 있다는 것이다. 그렇기 때문에 완전탐색, 백트래킹 등 다양한 탐색이 가능하다. 그래도 시간제한이 주어졌기 때문에 조건을 둬서 쓸데없는 탐색을 줄이는 편이 나아 보인다. 다른 건 다 제쳐두고 맵의 칸 하나의 관점으로 바라보자. 해당 자리가 비어있어서 숫자 1~9까지 하나를 넣어야 한다. 어떤 절차를 걸쳐서 넣을까? 스도쿠의 규칙에 따라 아래 세 곳에 똑같은 숫자가 있다면, 그 수는..

문제 이해 단계 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개의 좌석으로 이루어져 있고, 한 줄로 나열..