https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 설명 0과 1로만 이루어진수를 이진수라고 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 00101..

https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 설명 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며 돌은 1개, 3개 또는 4개를 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이긴다. 두 사람이 완벽하게 게임했을 때 이기는 사람을 구하는 프로그램을 작성해라. 게임은 상근이가 먼저 시작한다. 입력 1 C가 1개 -> S가 1개를 가져가서 S가 이긴다. 돌이 6개면 S가 4개 -> C가 1개 -> S가 1개를 가져가서 S가 이긴다. 돌이 7개면 S가 1개 -> C가 4개 -> S가 1개 -> C가 1개를 가져가서 C가 이긴다. 돌..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 설명 DP를 활용한 기본 문제이다. DP가 늘 그렇듯이 반복되는 규칙을 찾아내고 점화식을 구하면 된다. 이 문제의 경우 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구해야 한다. 단, 수는 한 개 이상 선택해야 한다. 예제 입력 1을 가지고 보도록 하자. 앞에서부터 구해보자. 먼저 수를 단 한 개 이상 선택해야 한다고 했으므로 현재 최댓값은 10으로 하자. 그 다음 수인 -4와 더..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 설명 고속도로에 센서들이 설치되어 있다. 그리고 이 센서들 사이에 집중국을 세워서 센서에서 얻은 데이터를 처리한다고 한다. 최대 K개의 집중국을 설치할 수 있다고 할 때 각 집중국의 수신 가능영역 거리의 합의 최솟값을 구하는 프로그램을 작성해야 한다. 처음 문제를 보면 무슨 말인지 잘 모를 확률이 높으니 예제 입력 1을 가지고 그림으로 보자. 주어진 센서는 위와 같이..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 2 4 5 --> 2 2 6 --> 3 으로 정렬되고 이를 알고리즘에 돌리면 결과는 3이 나온다. 이를 해결하려면 '시작하는 시간'을 기준으로 오름차순 정렬해야 한다. 그리고 힙 또는 우선순위 큐와 같..

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 문제 설명 행렬 A와 B가 주어진다. 이 행렬은 모두 0 또는 1로 구성되어 있다. A를 B로 변환하는 최소 연산을 구해야 한다. 연산 방법은 0이면 1로, 1이면 0으로 3x3만큼 변환한다. 풀이 방법 간단하게 생각하면 간단하고 어렵게 생각하면 한없이 어려운 게 그리디 문제인 거 같다. [0, 0] 부터 한 칸씩 이동하면서 해당 칸이 B와 다르다면 해당 위치부터 3x3의 모든 칸을 반전시키면 된다. 그리고 마..