INU 송년 코드페스티벌 2019 Open Contest 문제풀이



총 8 문제 였습니다.

(개인적으로 무난한 난이도로 구성되어 있다고 생각합니다.)

A. 펭귄추락대책 위원회 (백준 18228번)

총 N개의 얼음의 강도를 받으며,

펭귄이 위치한 얼음 기준, 왼쪽과 오른쪽의 최소를 받아 더해 출력하면 되는 간단한 문제였습니다.

B. 내가 살게, 아냐 내가 살게 (백준 18229번)

문제의 입력이 1번사람의 1~M번째 시도, 2번사람의 1~M번째 시도, ... 으로 주어졌습니다.

몇번째 시도에 주어진 K 값을 넘을 수 있는지 업데이트만 해주면 됐습니다.

이 역시 간단한 문제였습니다.

C. 2*N 예쁜 타일링 (백준 18230번) 

사용한 알고리즘 : Greedy

주어진 2*N 의 바닥에 2*1 A타일 , 2*2 B 타일을 갖고 가능한 최대로 이쁨을 채우는 문제였습니다.

우선 priority_queue(이후 pq)를 사용하여 A타일, B타일을 큰 순으로 정렬해주고,

(pq에 정렬된) 큰 순서대로 B타일을 바닥에 모두 깐 후,

만약 B타일을 모두 깔아도 바닥에 남는 부분이 있으면, 큰 순서대로 A타일을 채웠습니다.

A타일 2개가 차지하는 부피 = B타일 1개가 차지하는 부피 = 2*2 임을 생각하여,

바닥에 깔린 B타일을 역순으로 따라가며(역순이니 작은것 부터 보겠죠),

A타일 큰 것 2개 vs 깔린 B타일 작은것 1개 를 비교하여

A타일 큰 것 2개가 크다면 바꿔주는 과정을 반복하여 해결하였습니다.



D. 파괴된 도시 (백준 18231번) 

사용한 알고리즘 : 그래프이론


먼저, 각 도시간 연결 관계를 town이라는 벡터 행렬로 구성하고, boom 이라는 bool 행렬로 파괴된 도시들을 체크했습니다.

연결된 도시가 모두 파괴된 도시들은 무조건 폭탄이 터졌다고 생각하고,

모든 도시를 findbomb 함수로 돌리며, 폭탄이 터진 도시들을 bomb 라는 bool 행렬로 정리했습니다.

이후 폭탄이 터진 도시를 제외한 모든 도시를 possiblegraph 함수로 돌리며

1) 파괴된 도시일 경우, 연결된 도시 중 폭탄이 떨어진 도시가 있어야 함.

2) 파괴되지 않은 도시일 경우, 연결된 도시 중 폭탄이 떨어진 도시가 없어야 함.

을 체크해 주었습니다.

E. 텔레포트 정류장 (백준 18232번)

사용한 알고리즘 : BFS


텔레포트로 연결된 정거장들을 벡터 행렬로 구성하고 BFS를 돌리면 됩니다.

BFS를 돌릴시, 정거장에 텔레포트로 연결된 정거장들과, 양옆의 정거장을 queue에 넣어주면 됩니다.

이때 visited 라는 bool 함수를 만들어, 한번 방문한(queue에 넣은) 정거장은 다시 방문하지 않도록 했습니다.




F. 러버덕을 사랑하는 모임 (백준 18233번)

사용한 알고리즘 : DFS


우선 DFS 를 돌려 P명의 사람들 원하는 인형개수 합이 최소 <= E <= 최대 인 P 명을 찾습니다. (vector로 저장함)

찾은 P명의 사람들이 원하는 인형 개수 합의 최소를 MinA 라 하면,

P명의 각 사람들은 각각 자신들이 원하는 인형의 최소개를 갖고, 이 때 E-MinA 개를 P명에게 적당히 뿌려주면 됨을 생각 할 수 있습니다.

remain = E-minA라 하고, P명의 사람을 저장해 놓은 vector에서 한 명씩 봅시다.

vector에서 한명 뽑아 A 라 하고 이사람이 원하는 인형의 최소개수를 a, 최대 개수를 b라 합시다.

이사람은 앞서 생각한대로 일단 a 개를 갖고있고, 추가로 b-a개 까지 갖을 수 있습니다.

(1) b-a < remain 인 경우

A가 b-a만큼 추가로 갖는다. (결과적으로 A는 총 b개를 갖는다.)

이후 remain = remain - (b-a) 를 취한 후, 다음사람으로 같은 과정 반복.

(2) b-a > remain 인 경우

A가 remain만큼 추가로 갖는다. (결과적으로 A는 총 a + remain개를 갖는다.)

이때 remain = 0 입니다.

G. 당근 훔쳐 먹기 (백준 18234번)

사용한 알고리즘 : 수학.....



집중해야 하는 부분은 w (심는 당근) < p (영양분) 이라는 점, N (당근개수) < T (일수) 라는 점입니다.

이 두 조건을 통해 생각해보면,

당근을 첫날 심은 후, 최대한 놔두고, 각 한번씩만 뽑는 것이 최대의 맛을 갖을 수 있는 방법입니다.

사실 이것만 알면 끝입니다.....





H. 지금 만나러 갑니다. (백준 18235번)

사용한 알고리즘 : DFS, 비트마스킹

두 오리 A, B 사이의 거리를 L이라 하자. (A의 위치 < B의 위치 라고 생각합니다.)

두 오리의 움직임은 다음 4가지와 같습니다.

1) A 가 왼쪽 B가 왼쪽

2) A가 오른쪽 B가 오른쪽

3) A가 오른쪽 B가 왼쪽

4) A가 왼쪽 B가 오른쪽

움직임 1), 2) 의 경우 L 값이 유지됩니다.

움직임 3) 의 경우 L 값이 줄어듭니다.

움직임 4) 의 경우는... 딱히 생각 안해줘도 됩니다......

각 오리는 n일차에 2^(n-1) 만큼 뛰므로, L이 홀수 이면, A, B 가 만날 수 없음은 자명합니다.

또한 오리가 가까워 질때는 2*2^(n-1) = 2^n 만큼 가까워 집니다. (ex) 2일차에는 2^2 = 4만큼 가까워집니다.)

예를 들어 두 오리 사이의 거리가 L = 11 인 경우를 생각해보면,

11을 이진법으로 나타내면 1011 입니다.

즉 1일차, 2일차에 가까워지고(움직임 3), 3일차에 거리를 유지하며(움직임 1or2), 4일차에 다시 가까워 지면 됩니다.

이를 생각하면, 주어진 L에서,

가까워 져야 하는 일차는 신경 쓸 필요 없이,

거리를 유지해야 하는 날에서 움직임 1) 혹은 2) 가 주어진 땅 내에서 가능한지만 확인하면 됩니다.

이를 DFS 함수로 확인하면 됩니다.



이상 INU 송년 코드페스티벌 2019 Open Contest 문제풀이였습니다.

처음 써보는 거라 부족한 점이 많습니다..... 죄송해요....

감사합니다.