방앗간 개발자

문제 출처:https://www.acmicpc.net/problem/1365

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

이런 문제를 처음 풀어본다면 대체 어떻게 접근해야 하는지 감이 안잡힐 수도 있지만  

몇가지 예시를 들어 문제를 풀어보면 한 가지 패턴을 찾을 수 있습니다. 

입력: 7    3    1    2    0    6    8    9    4    10 

이런 전선 입력이 주어졌다면 여기서 꼬이지 않고 전선을 잘라내는 방법은 

7    3    1    2    0    6    8    9    4    10

빨간색으로 칠한 전선을 잘라내는 것 입니다. 전선을 잘라내고 남아있는 전선(1, 2, 6, 8, 9, 10)을 보면 한 가지 패턴이 있는데 

바로 '증가하는 수열' 이라는 겁니다.

따라서 이 문제는 어떤 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수를 제거하여 만들 수 있는 부분수열 중 오름차순으

로 정렬된 가장 긴 수열을 찾는 최장 증가 부분 수열(LIS : Longest Increasing Subsequence)알고리즘을 이용하여 푸는 문제

입니다.

이 LIS알고리즘은 O(n^2)과 O(n log n)의 시간이 걸리는 알고리즘이 각각 있지만 이 문제에선 최대 입력이 100,000이므로 

O(n^2)의 알고리즘을 사용하면 시간초과에 걸립니다. 따라서 저는 O(n log n)의 알고리즘을 소개하고 문제를 풀겠습니다.

O(n log n)의 알고리즘에선 이진탐색을 약간 변형한 알고리즘인 Lower bound를 사용하게 됩니다. 

입력값은 위에 예시로 든 수열을 그대로 사용하겠습니다.

입력: 7    3    1    2    0    6    8    9    4    10

1. 벡터를 하나 만들어 줍니다.

2. 수열을 처음부터 검사하는데 현재 검사하는 수를 A라고 했을때 벡터의 마지막 요소를 비교하여 

    - A 가 벡터의 마지막 요소보다 크면 벡터의 마지막에 추가해준다.

   - A 가 벡터의 마지막 요소보다 작으면 Lower bound하여 나온 index위치의 값과 교환해준다.

3. 최종적으로 만들어진 벡터의 길이 N이 최장 증가 수열의 길이가 된다.

그림으로 하나하나 표현하면 아래와 같습니다.

이렇게 최종적으로 만들어진 수열(0, 2, 4, 8, 9, 10)의 길이가 LIS의 길이가 됩니다.

문제의 정답인 잘라야 하는 전선의 수는 주어진 (n - LIS의 길이)를 하면 나오게 됩니다.

단 이 문제에서는 LIS의 요소를 요구하지는 않았는데 위에서 구해진 수열이 LIS를 나타내는건 아닙니다.

직접 눈으로 확인해봐도 수열 7    3    1    2    0    6    8    9    4    10 의 최장 증가 수열은 

1    2    6    8    9    10 이지만 LIS알고리즘을 통하여 구해진 수열은 0    2    4    8    9    10 입니다.

따라서 LIS의 요소까지 구하려면 추가적인 작업을 해야하지만 그 방법은 다음 문제에서 알아 보도록 하겠습니다.

전체 코드입니다.

문제 출처:https://www.acmicpc.net/problem/6064

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다. 

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

문제 자체가 약간 난해한 면이 있지만 몇번 읽어보면 규칙을 파악 할 수 있을겁니다.

해를 표현하는 방법은 문제에 나와있는 그대로 <M:N> 이 주어졌을때 년도를 <X:Y>로 표현한다면 X,Y는 1,1로 시작해서 

1씩 증가하며 X>M이 되면 X%M, Y>N이 되면 Y%N을 해주면 됩니다. 

따라서 문제로 M,N,X,Y가 주어졌을때 <X,Y> 가 몇번째 해인지 알기 위해선 위의 조건을 적용시켜 1,1부터 시작하여 증가시키

며 검사하면 됩니다. 그러나 문제는 <X,Y>로 표현할 수 없는 해가 주어진다는 것인데 이 때 무한 반복을 하지 않으려면 처음

부터  반복의 끝을 정해주어야 합니다.

그리고 이 반복의 끝이 바로 문제에 나오는 '종말의 해' 인데 이 날을 구하는 방법은 바로 N과 M의 최소 공배수를 구하는 것입

니다. 이 N과 M의 최소공배수를 G라고 한다면 이 G번째 해가 달력의 마지막이기 때문에 첫번째 해부터 G번째 해까지 <X,Y>

로 표현되는 해가 없다면 <X,Y> 가 유효하지 않은 표현이고 따라서 -1을 출력해주면 되는겁니다.

최소 공배수를 구하는 방법은 유클리드 호제법을 이용하였습니다. 

최대 공약수 공식(gcd)

1. a,b: 최대 공약수를 구하고자 하는 두 수 

2. r: a를 b로 나눈 나머지 r=a%b

3. 식: gcd(a,b)=gcd(b,r) 을 b가 0이 될때까지 반복해주면 됩니다.

최소 공배수 공식(lcm)

1. a,b: 최소 공배수를 구하고자 하는 두 수

2. gcd(a,b): a,b의 최대 공약수

3 식: a*b/gcd(a,b)

전체 코드입니다.

문제 출처:https://www.acmicpc.net/problem/14697

정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 개 있다. 정보 초등학교에서는 학생들에게 이 방들을 배정하되, 배정된 모든 방에 빈 침대가 없도록 하고자 한다.

예를 들어, 방의 종류가 5인실, 9인실, 12인실이고 6학년 여학생 전체가 113명 이라면, 5인실 4개, 9인실 5개, 12인실 4개를 예약하면 각 방에 남는 침대 없이 배정이 가능하다. 또한 12인실은 사용하지 않고 5인실 10개와 9인실 7개만 사용하는 것도 가능하다. 그러나 방의 종류가 3인실, 6인실, 9인실이고 6학년 여학생 전체가 112명이라면 빈 침대 없이 방을 배정하는 것은 불가능하다.

방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수를 나타내는 자연수 하나가 주어졌을 때, 배정된 모든 방에 빈 침대가 없도록 방 배정이 가능한지를 결정하는 프로그램을 작성하시오. 단, 세 종류의 방은 모두 충분한 개수가 있다고 가정하며, 위의 예에서와 같이 세 종류의 방을 모두 활용하지 않고 한 종류 또는 두 종류의 방만 이용하여 배정하는 것도 허용한다.

표준 입력으로 방의 정원을 나타내는 서로 다른 세 자연수 A, B, C (1 ≤ A < B < C ≤ 50)와 전체 학생 수를 나타내는 자연수 N (1 ≤ N ≤ 300)이 공백으로 분리되어 한 줄에 주어진다.

빈 침대 없이 배정이 가능할 경우 표준 출력으로 1을, 불가능할 경우 0을 출력한다.

문제의 입력이 크지 않기 때문에 모든 경우O(n^3)를 탐색해도 시간안에 충분히 문제를 풀 수 있습니다.

따라서 재귀나 3중 포문을 이용하여 문제를 풀 수 있는데 저는 3중 포문을 이용하여 풀었습니다.

한가지 세 종류의 방을 전부 활용하지 않아도 된다는 점만 주의하면서 풀면 됩니다.