투투

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 ..

문제 N개의 집이 수직선 위에 놓여있다. 여기서 C개의 공유기를 설치하려고 한다. 한 집에 공유기를 하나만 설치하여 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하려면 얼만큼의 거리로 C개의 공유기를 놓아야하는지 구하라 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. 출력 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다. 접근 이분탐색으로 접근을 하였다. 공유기를 설치한 집의 거리를 D라고 할 때 C개를 설치한 집들간의 거리가 D이상이 되어야한다. 예를 들어 ..

문제 절단기로 한 줄에 나열되어 있는 나무를 잘라서 M미터의 나무를 구하려고 한다. 절단기는 고정이 되어있고 높이를 조절하여 해당 높이만큼 나무를 자를 수 있다. N개의 나무 중 절단기로 잘라서 M미터의 나무를 가지려고 할 때 절단기의 최대 높이를 구하라. 정확히 M미터를 가져가지 못하는 경우는 없다. 입력 첫째 줄에 N과 M을 입력하고 이어서 N개의 나무를 입력한다. 출력 절단기의 최대 높이를 출력한다. 접근 이분탐색을 연습해보았다. 구하려고하는 것은 절단기의 최대높이이다. 따라서 절단기의 높이를 조절하여 M미터를 가져갈 수 있는지 탐색을 해야한다. 절단기의 높이를 나무들의 최소높이부터 최대높이까지 탐색하면서 구하기에는 오래걸린다. 따라서 절단기의 높이를 1과 나무의 최대높이의 중간값으로 시작하여 찾아..

문제 K개의 랜선이 있을 때 각각 같은 길이로 잘라서 N개의 랜선을 만든다. 자르고 남은 길이는 사용할 수 없고 N개보다 많이 만들어도 된다. 이때 최대 어느 길이로 잘라야 N개를 만들 수 있는지 구하라. 입력 첫째 줄에 K, N을 입력한다. (K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수) 이어서 K 줄에 걸쳐서 랜선의 길이가 주어진다. 랜선의 길이는 2^31-1보다 이하이다. 출력 N개를 만들 수 있는 랜선의 최대 길이를 출력한다. 접근 이 문제를 통해 이분탐색이 무엇인지 알았다. 이분탐색은 어떠한 범위의 값에서 특정한 값을 찾을 때 범위를 두 개로 나눠서 찾아보는 것이다. 가장 작은 값과 가장 큰 값을 더한 중간값을 찾고 중간값을 기준으로 찾아야하는 수와 비교했을..

문제 L개의 알파벳 소문자로 구성되어 있는 암호가 있다. 암호는 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어야 한다. 그리고 암호는 알파벳이 증가하는 순서대로 배열되어 있다. C개의 알파벳이 주어졌을 때 L개의 알파벳을 선택하여 만들 수 있는 암호를 출력하라 입력 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. 출력 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다. 접근 백트래킹 연습을 위해 풀었다. 알파벳을 하나 선택할 때마다 모음과 자음을 카운트한다. 그리고 L개의 알파벳을 골랐을 때 문제의 조건에 부합된다면 출력하도록 구현하였다. 구현 알..

문제 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. 출력 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다. 접근 백트래킹을 연습하고자 했다. 백트래킹으로 만들 수 있는 수열을 만들어 계산을 하고 최댓값을 비교한다. 구현 solve함수에서 수열을 생성한다. 현재 수를 선택하지 않았다면 선택을..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 접근 1번부터 N번까지 큐에 넣고 큐가 빌 때까지 다음을 반복한..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 출력 첫째 줄에 입력으로 주어진 M..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 접근 처음에는 단순하게 리스트에 N개의 수를 넣고 또 다른 리스트에 M개의 수를 넣어 for문으로 탐색하면서 in연산을 사용하였다. 하지만 리스트를 탐색하는 것은 O(N)의 시간복잡도가 발생하여 시간초과가 발생하였다. 이를 set이나 dict 자료형을 사용하면 O(1)의 시간복잡도를 갖기 때문에 효율적이라는 것을 알게되었다. 구현 N개의 수를 set 자료형으로 입..

문제 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제된다. 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소의 크기는 NxN이며 빈 칸, 벽, 바이러스로 이루어져 있다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 활성화된다. (0은 빈 칸, 1은 벽, 2는 바이러스) M개의 바이러스를 선택하여 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구한다. 입력 첫째 줄에 N(4이상 50이하)과 바이러스 개수 M(1이상 10이하)를 입력한다. 이어서 NxN의 연구소 맵을 입력한다. 출력 모든 빈 칸이 바이러스가 되는 최소시간을 구하고 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다. ..