Platinum/Platinum I2 BOJ 1733 : 등번호 문제 링크 : https://www.acmicpc.net/problem/1733 N명의 사람이 앞 뒤에 숫자가 적힌 유니폼을 갖고 있다. 각자 앞 또는 뒤에 적힌 숫자를 골라 N명의 사람이 고른 숫자가 겹치지 않게 하는 해를 출력하면 되는 문제다. 처음에 문제를 보자마자 든 생각은 이게 왜 플레1 이나 하지? 였다. 그냥 이분매칭인데, 단순한 이분매칭은 플레4~5 이기 때문이다. 하지만 N 제한이 100만인 것을 알고 납득했다. 혹시 새로운 이분매칭 알고리즘을 배워야만 하나? 하고 검색하니 Hopcroft - Karp 가 있긴 했다. 그래도 O(N 루트 N) 이라 시간초과 뜰 것 같아 다른 해법을 고민하기 시작했다. 약간의 관찰을 통해 그래프 탐색 느낌이 난다는 것을 알게 되었다. 예를 들어 1번 학생이.. 2022. 8. 16. BOJ 7765 : Supersquare 문제 링크 : http://acmicpc.net/problem/7765 500이하의 자연수 N을 입력받으면, 2N 자리 제곱수를 출력하면 된다. 단, 앞 N자리와 뒤 N자리 또한 제곱수여야 한다. 지금 내가 서술하는 풀이가 정해라면 그리 좋은 문제 같진 않다... Naive 하게 코드를 돌려보면서 규칙을 찾아봤는데 꽤 오래걸렸다. 규칙 찾고 정리하는데 3일 정도 걸렸다. 3일 내내 잡고 있었던 건 아니지만 꽤 어려웠던 건 확실. N이 짝수일 때 (N = 2n + 2 형태) ( 5 * 10(2n+1) - 10(n+1) + 1 )2 를 전개하면 앞 (2n+2) 자리는 (5 * 10n - 1)2 이고 뒤 (2n+2) 자리는 (10(n+1) - 1)2 이다. 이걸 한번에 발견한 것은 아니고 물론 Naive 하게.. 2022. 8. 14. 이전 1 다음
