2623 음악프로그램 (G3) 각 PD들의 가수 출연 순서에 따라 단방향 그래프를 만든다. 그 다음에 Topological Sort를 해줘서 전체 출연 순서를 정한다. Directed Acyclic Graph를 이루면 전체 가수의 수만큼 정확히 출력이 될것이고 아니면 순서 정하는 것이 불가능하므로 0을 출력한다. http://boj.kr/09f1e0b6e82c457e89e3a05fb6143178 4386 별자리 만들기 (G3) 각 별들의 좌표를 정점으로 생각하고 좌표들 간의 거리를 간선으로 생각하면 그래프를 구성할 수 있다. 그리고 Minimum Spanning Tree를 구성하면 별자리를 만드는 최소 비용을 구할 수 있다. http://boj.kr/a587be0a5a53456583384ae27fbc0..
8/22 Problem Solving
2825 수업시간에 교수님 몰래 교실을 나간 상근이 (G2) 비트 마스크로 0~9 사이의 숫자가 포함되어 있는지 여부를 상태로 표현해서 세준다. 쌍의 개수를 세줄 때 자기자신끼리의 쌍과 중복되는 쌍은 제거해야한다. http://boj.kr/065bfe2aa12a4a85abb60aed0ed3d74a 17497 계산기 (G2) 처음에는 BFS로 생각했는데 경우의 수가 최대 4^99가 되서 불가능하다. 연산이 전부 2와 연관이 있는것에 주목하자. 2를 더하는 것은 1번째 비트에 1를 추가하는 것과 같고 빼는 것도 마찬가지이다. 곱하기는 left shift, 나누기는 right shift와 같다. 우리가 구해야 하는 것은 0에서 N까지 가는 방법인데 N에서 0으로 만드는 방법을 생각해보자. 1. 0번째 비트에..
오늘부터 연말까지 골드 문제 중에 랜덤으로 최소 5문제 이상씩 풀어보려고 한다. 골랜디가 80% 이상 방어되는게 목표다. 꾸준히 해보자.. 1477 휴게소 세우기 (G4) 처음에는 priority queue를 이용해서 greedy하게 m번에 걸쳐서 제일 큰 구간을 반씩 자르면 될것이라고 생각했다. 근데 생각해보니까 한 구간을 여러번 분할하는게 답이 되는 경우도 있어서 이 접근은 틀렸다. 구간의 최댓값의 최솟값이 될 수 있는 범위를 후보로 놓고 parametric search를 해서 답을 찾으면 된다. http://boj.kr/4481a6d19d05480db5e86a48da136770 2473 세 용액 (G3) 일단 정렬한 후에 모든 용액에 대해 하나의 용액을 fix하고 나머지 두 개의 용액에 대해서 ..