![]()
문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 문제 풀이 문제를 읽고 누적합을 구해서 소형차를 배정하는 문제인 것 같았다. 문제에서 주어진 테스트케이스에 대해서 먼저 누적합에 대한 그림을 그려보았다. 처음으로 접근한 방법은 정해진 구간까지의 최대 누적합을 구하는 방법으로 접근했다. 예를 들어 50까지 접근했을때의 최댓값은 40과 50을 태운 90이다. 다음으로 10까지 접근했을때의 최댓값은 40과 50을 태운 90 vs (35+40..
![]()
문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 이전의 선택한 색에 따라 다음 선택이 영향이 받는 문제였고, 배낭 문제와 굉장히 유사하게 느껴졌다. 배낭 문제와 같이 물건을 담으면서, 해당 물건을 담을 경우와 담지 않을 경우를 나눠서 계산하는 것처럼 해당 문제도 색깔을 선택할 경우와 선택하지 않을 경우를 나눠서 계산하는 문제였다. 우선 그림을 그려가면서 가장 먼저 발견한 조건은 k가 n의 절반보다 크다면 경우의 수는 0이라는 점이다. 이는 문제에서도 ..
![]()
문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 풀이 문제의 분류가 위상정렬인 줄 모르고 풀었다. 어쩌다 보니.. 위상정렬처럼 풀었다. 단순하게 입력단계에서 A와 B를 구분하는 과정에서 B로는 들어왔지만 A로 한 번도 들어오지 못한 녀석이 맨 뒤에 서야한다는것은 알았다. 입력에 대해서 도식화를 해보면 오른쪽과 같은 관계도가 나온다. 그림을 통해서 3가지 분류를 할 수 있다. 선택을 받지 못한..
![]()
문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 풀이 처음에는 점 하나를 잡고 탐색을 해서 정사각형을 판별하는 문제로 생각했는데, n과 m이 각각 1000이라 모든 점에 대해서 탐색하기가 무리가 있었고, 그 점에 대한 정사각형을 판별하는 과정도 굉장히 문제가 있었다. 그러다 무작정 그림을 그리다 보니 규칙을 발견할 수 있었다. 정사각형이란 모두 1로 이루어져야 하고, 가로와 세로의 길이가 같아야 한다. 하나의 점에서 2x2의 정사각형인지 판단하는 방법은 간단했다. 3가지 방향에 대해서 0이 없어야 한다...
![]()
문제 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 문제 풀이 확률과 통계를 하셨던 분이라면 자주 접했을 문제라고 생각합니다. 바로 도로를 주고, 도로를 통해 이동할 수 있는 경우의 수를 계산하는 문제입니다. 문제의 특이한 점은 이동하지 못하는 도로를 만들어서, 경우의 수를 제한한다는 점입니다. 확률과 통계에서 풀었던 것처럼 기본적으로 맨 위와 맨 왼쪽은 경로의 수가 1로 고정입니다. 최단 거리의 경우는 직진으로 갈 수밖에 없..
![]()
문제 https://www.acmicpc.net/problem/27210 27210번: 신을 모시는 사당 칠할 수 있는 돌상의 개수에 제한은 없으며, 반드시 연속한(인접한) 돌상들만 칠할 수 있음(띄엄띄엄 칠할 수 없음)에 유의하라. www.acmicpc.net 문제 풀이 같은 방향의 돌상의 길이가 가장 큰 구간을 구하는 전형적인 누적합 문제였습니다. 나는 두 개의 변수를 사용해서 각기 다른 돌상의 개수를 계산했습니다. 왼쪽 돌상의 개수를 left, 오른쪽 돌상의 개수를 right로 관리했습니다. 입력을 탐색하면서, 왼쪽 돌상이라면 left ++, right -- 오른쪽 돌상이라면 right++, left--를 해줬습니다. 추가적으로 우리는 연속적인 구간의 최대합을 원하기 때문에 left와 right가 ..
![]()
문제 https://www.acmicpc.net/problem/28082 28082번: 기계오리 연구 인하대학교 기계공학과의 기계오리 연구실에서는 2023년 버전 기계오리를 완성하기 위해 실험을 진행하고 있다. 실험 도중, 기계오리에 1개 이상 $K$개 이하의 배터리를 삽입하면 기계오리가 언 www.acmicpc.net 문제 풀이 대표적인 DP유형 중의 한 문제였던 것 같다. 나는 항상 DP 문제를 풀 때 처음에는 dp 배열을 2차원으로 접근하려고 한다. N개의 배터리중에서 배터리를 최대 k개 사용해서 만들 수 있는 전력량의 합을 목표로 점화식을 세워보기 전에 그림으로 그려보자. 주어진 예제를 바탕으로 간단하게 그림을 그려보았다. 최대 k개를 사용해서 구할 수 있는 전력량의 합을 계산하기전에 배터리를 통..
![]()
문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 풀이 사실 대표적인 DP문제이다. DP 문제는 차근차근 손으로 할 수 있는 만큼 해보는 것이 좋다고 생각한다. n = 0인 경우 3*0의 크기의 벽을 채우는 경우의 수는 공집합이라는 느낌으로 1로 생각했다. n = 1인 경우 3*1 크기의 벽은 주어진 도형을 통해서 채울 수 없다. 직접 그려보면 알 수 있다. n = 2인 경우 3개의 모양으로 채울 수 있다. n = 3인 경우 dp 문제이기 때문에 그 전에 구했던 도형들을 최대한 이용해보려고 했다. 3*3의 사각형인 경우 3*2 사각형과 3*1 사..
![]()
문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 풀이 해당 문제는 소수에 대한 판별을 최적화할 수 있는지와 투 포인터를 알고 있는지를 묻는 문제라고 생각한다. 소수에 대한 판별은 학부생 때 에라토스테네스의 체를 이용해서 최적화하는 방법은 배웠었다. 이제 시간복잡도를 계산해보자. N*2에 해당하는 반복문 2개로, 연속된 소수의 범위를 설정해서 합을 구할 수도 있다. 하지만 N의 최댓값이 4,000,000이고, 그에 따른 소수의 개수는 알지 못해도 소수의 개수가 100,000개만 돼도 N^2이면 10,000,000,000이라 시간 초과가 난다. 따라서 해당..
