Coding Test

1. 문제 설명 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 2. 아이디어 보자마자 bfs를 떠올렸으나 예외 처리가 귀찮을 거 같아서 재귀 호출로 접근법을 바꿔보려 했지만, 그렇게 되면 4방향으로 재귀를 호출하니 O(4^N)의 시간 복잡도가 나오므로 포기했다. (다 풀고 보니 조건만 잘 걸어준다면 가능했을 것 같긴 하네) int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i=0; i item; ..

1. 문제 설명 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 시험 끝나면 코테 매일 한 문제씩 풀려고 벼르고 있었는데, 뭔 놈의 과제랑 쪽지 시험이 계속해서 쏟아진다. 그래서 쪽지 시험 반 쯤 던지고 풀었는데, 이딴 게 골드 3 2. 아이디어 가장 처음 보자마자 별 하나씩 트램펄린 꼭짓점에 두고 4방향을 뒤지면 될 거라고 생각했다. 이걸 문제를 보자마자 떠올렸는데, 가장 최근에 공부한 게 탐욕법이라서 그런가. 그런데 상식적으로 점 ..

1. 문제 설명 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net 이제 MT 갈 때 됐으니, MT 문제를 풀어보라던 스터디원의 권유로 보게 된 문제. 오랜만에 코테 문제 푼다고 새벽 3시까지 못잤다. 장장 10시간 정도를 풀었던 것 같다. 🤮 물론, 그 사이에 프로젝트 때문에 개발을 멀티로 수행했다는 것도 문제였던 거 같기도 한데, 문제만 봤어도 금방은 못 풀었을 것 같다. 2. 아이디어 보자마자 위상정렬(Topological Sort) 문제겠거니 했다. "내가 가려면 누군가(선행조건)가 가야 한다."식의 문제이므로, '나'의..

1. 문제 설명 요새 너무 바빠서 문제 하나 풀 여유조차 없다는 게 너무 서러워서 골드 문제라도 오랜만에 풀어봤다. 플래티넘은 푸는데 시간이 얼마나 소요될 지 감이 안 잡혀서 ㅠㅠ 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 2. 아이디어 이 문제를 처음 보자마자 vertex cover 문제로 접근하면 되겠구나 싶었다. (그러면 이분 매칭 문제로 바뀐다.) 하지만 조금 더 생각을 해보자. 가중치가 따로 존재하진 않으므로, 유량을 1로 전부 고정시키고 포스 풀커슨 알고리즘을..