방앗간 개발자

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

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 최소 개수의 전깃줄을 구하는 프로그램을 작성하시오.

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다. 둘째 줄부터 한 줄에 하나씩 없애야 하는 전깃줄의 A전봇대에 연결되는 위치의 번호를 오름차순으로 출력한다. 만약 답이 두 가지 이상이라면 그 중 하나를 출력한다.

바로 전 게시글에서 이어지는 문제입니다.

이번에도 없애야 하는 전깃줄의 최소 개수를 출력하는데 플러스로 없애야 하는 전봇대의 위치까지 알아내야 합니다.

일단 전 게시글에서 알려준 방법으로 없애야 하는 전봇대의 최소 길이부터 구해봅시다.

LIS의 길이를 구하는 방법을 모른다면 (1365번: 꼬인 전깃줄) 를 보고 오시면 됩니다.

예시는 위 그림에 있는 수열[ 4, 2, 6, 7, 9, 1, 3, 10 ]을 그대로 쓰겠습니다. 

위 수열에 LIS알고리즘을 사용한다면 [ 3, 6, 7, 9, 10 ] 의 결과가 나옵니다 이 수열의 길이가 LIS의 길이가 됩니다. 

단 이 수열이 LIS을 구성하는 수열은 아닙니다 딱 보더라도 제일 앞에 있는 3은 원본 수열에서 뒤쪽에 있는 수입니다. 

따라서 LIS의 요소까지 구하려면 추가적인 연산을 해주어야 하는데 이제부터 그 방법을 설명 하겠습니다.

일단 기존에 하던대로 LIS알고리즘을 수행합니다 단 수행하면서 입력되는 수가 LIS배열의 몇 번째 칸에 들어가는지 기록 

할 배열이 하나 더 필요합니다. 그림으로 표현하면 아래와 같습니다.

이 구해진 Record배열의 제일 뒤부터 순차적인 내림차순 즉 Record 배열의 제일 마지막이 5 이므로 5, 4, 3, 2, 1순으로 

원본 배열의 인덱스에 맞춰 데이터를 추가해주면 LIS 의 요소를 구할 수 있습니다. 

최종적인 수열 [ 2, 6, 7, 9, 10 ] 이 LIS 요소까지 구성하는 수열이 됩니다.

문제의 정답은 LIS를 만들기 위해 없애야 하는 전봇대를 구하는 것 입니다. 

따라서 원본 수열에서 최종적으로 구해진 LIS의 요소들을 전부 빼고 남은 숫자들이 없애야 하는 전봇대가 됩니다.

전체 코드입니다.

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

<그림 1>과 같이 정사각형 모양을 한 여섯 종류의 색종이가 있다. ①번 색종이는 한 변의 길이가 1cm이고, 차례대로 그 길이가 1cm씩 커져, ⑥번 색종이의 한 변의 길이는 6cm가 된다.

주어진 색종이를 <그림 2>와 같이 가로, 세로의 길이가 각각 6cm인 판 위에 붙이려고 한다. 색종이를 붙일 때는 색종이가 판의 경계 밖으로 삐져 나가서는 안되며, 색종이가 서로 겹쳐서도 안 된다. 또한 하나의 색종이는 하나의 판에만 붙여야 한다.

각 종류별로 색종이의 장수가 주어질 때, 그 색종이를 모두 붙이기 위해서 위와 같은 판이 최소 몇 개가 필요한지 구하는 프로그램을 작성하시오.

첫째 줄부터 여섯째 줄까지 각 종류의 색종이의 장수가 ①번부터 ⑥번까지 차례로 주어진다. 각 종류의 색종이의 장수는 최대 100이다.

첫째 줄에 필요한 판의 최소 개수를 출력한다.

가장 큰 색종이부터 판에 붙여주면서 남는 공간에도 들어갈수 있는 가장 큰 색종이를 넣어주는 식으로 문제를 풀었습니다. 

판의 크기가 크지 않고 색종이의 종류도 얼마 안되어서 경우의 수를 전부 계산하여 그림으로 나타내면 

일단 6번 색종이는 판에 꽉 차므로 다른 색종이를 더 넣을 수 없습니다.

5번 색종이는 

위와같이 1개만 들어갈 수 있고 나머지 공간은 전부 1번 색종이로 채울 수 있습니다.

4번 색종이는

위와같이 1개만 들어갈 수 있고 나머지 공간에 2번 색종이가 최대 5개 들어갈 수 있습니다.

2번 색종이가 5개 이하라면 나머지 공간엔 1번 색종이로 채워주면 됩니다.

3번 색종이가 경우의 수가 여러가지 있는데

이렇게 전부 3번 색종이로만 채워진다면 최대 4개가 채워집니다.

3번 색종이가 3개만 채워진다면 나머지 공간에 2번색종이가 1개 들어갈 수 있고

나머지 공간은 1번 색종이로 채워줍니다.

3번 색종이가 2개만 채워진다면 2번 색종이는 최대 3개 채워지고 

나머지 공간은 1번 색종이로 채워줍니다.

3번 색종이가 1개만 채워지면 2번 색종이는 최대 5개 채워지고

마찬가지로 남는 공간은 1번 색종이로 채워줍니다.

2번 색종이는

위와같이 최대 9개까지 채울 수 있습니다.

남은공간이 있다면 1번 색종이로 채우면 됩니다.

위와같은 과정을 거치고도 1번 색종이가 남아있다면 한판에 최대 36개가 들어갈 수 있으니 

남아있는 1번 색종이의 수에 맞춰 판을 추가해줍니다.

이런방식으로 주어진 색종이에서 최소 몇개의 판이 필요한지 구할 수 있습니다. 

아래는 전체 소스입니다.

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

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

문제 자체는 DFS나 BFS를 이용하여 조건에 맞추어 인구 이동이 가능한 영역을 구하고 이 영역 안에서 인구 이동을 시킵니다.

이 인구 이동을 더 이상 불가능 할때까지 계속 반복하며 인구이동 발생 수를 체크만 해주면 되는 비교적 간단한 문제인데 

저는 문제에서 말하는 '인구 이동'을 잘 못 이해하여 문제를 푸는데 한참 걸렸습니다.

제가 헷갈린 인구 이동은 아래와 같습니다.

L = 10, R = 50

이런 형태로 입력이 주어졌다고 합시다.

주어진 배열에 대하여 인구 이동이 가능한 영역을 위와같이 구해줍니다.

조건에 맞게 배열을 변형시켜준 뒤 인구 이동 횟수를 1 증가시킵니다. 

변형된 배열에 맞추어 한번 더 인구 이동이 가능한 영역을 구합니다.

여기서 한 구역을 조건에 맞추어 바꿔주었는데 이 때 인구 이동 횟수를 1 증가시키면 안됩니다. 

이렇게 모든 영역을 전부 다 바꿔준 뒤에야 인구 이동 횟수를 1 증가시켜주어야 합니다.

저는 처음에 구역 한개가 바뀔때마다 인구 이동 횟수를 증가시키는 줄 알고 한참을 고생했습니다.

이 부분만 주의해서 풀면 그렇게 어렵지 않게 풀이가 가능할거라 생각됩니다.

그리고 더 이상 인구 이동이 가능하지 않아서 프로그램을 종료하는 조건은 저의 경우 아래와 같은

형식으로 풀었습니다.

위의 배열에 대하여 영역을 구했을때 똑같은 크기의 배열을 하나 더 만들어 아래처럼 숫자로 각 구역을 

표시 해 주었습니다. 따라서 어떤 배열이 주어졌을때 아래처럼 영역을 숫자로 나타낸 배열이 

이와 같은 형식을 나타낸다면 모든 구역이 전부 독립적인 영역을 가진다는 의미이므로 이 때 프로그램을 

종료시켜 주었습니다.

전체 코드입니다.