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

문제 이해 단계 문제가 이해하기가 어려웠는데 최대한 쉽게 풀어써보겠다. 전체 문자열이 존재하고 하나씩 드러나게 하는데 이걸 전체 단어로 볼 때 사전순으로 가장 빠르게 하는 것이다. 앞에 있는 알파벳이 높을수록 사전순으로 빠르기 때문에 맨 앞부터 높은 알파벳부터 채우는 것이다. 예제 출력 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개의 같은 바..