상위 99.99%의 PS

www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net Greedy 큰 수는 111..., 7111... 의 형태이고, 작은 수는 ???88888...의 형태이다. 노트에 몇번 끄적이다 보면 보인다. 큰 수는 홀수 짝수, 작은수는 7로 나눈 나머지에 따라 케이스를 나누어 풀어주면 된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import sys input = sys.stdin.readl..

www.acmicpc.net/problem/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net 편의시설을 집으로 쓸 수 없다는 조건이 없기 때문에, 문제가 매우 쉬워졌다. 그냥 편의시설을 집으로 쓰면 된다. 집과 가장 가까운 편의시설의 거리는 0이 되므로, 가장 먼 편의시설과의 거리만 계산해주면 O(N^2)에 풀 수 있다. N제한도 1000밖에 되지 않아 충분하다! 집을 편의시설로 정하는게 왜 되는건지는 직접 증명..

www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 비트마스킹 맨 윗줄은 2^10가지의 경우를 모두 테스트하고, 2번째 줄부터 그 위 전구가 켜져있으면 스위치를 누르는 방식으로 쭉 진행하면 된다. 그러고 마지막줄까지 진행한 후, 마지막줄에 켜져있는 전등이 있는지 확인하면 된다. 레퍼런스 당해서 힘들었다.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3..