[BaekJoon] #11328 - Strfry [Java][C++]
문제 링크 1. 아이디어 strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어내는 함수로 1번째 문자열에 대해 2번째 문자열이 strfry 함수를 통해 얻어질 수 있으려면 두 단어가 애너그램 관계에 있으면 된다. 따라서 카운팅 배열을 활용해서 1번째 단어의 문자를 카운팅 배열에 더하고 2번째 단어의 문자를 카운팅 배열...
문제 링크 1. 아이디어 strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어내는 함수로 1번째 문자열에 대해 2번째 문자열이 strfry 함수를 통해 얻어질 수 있으려면 두 단어가 애너그램 관계에 있으면 된다. 따라서 카운팅 배열을 활용해서 1번째 단어의 문자를 카운팅 배열에 더하고 2번째 단어의 문자를 카운팅 배열...
문제 링크 1. 아이디어 $N$개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구해야 하는 문제로 다이나믹 프로그래밍을 활용하면 해결할 수 있다. i개의 카드가 들어있는 카드팩의 가격을 arr[i]로 정의하고, dp 테이블에서 dp[i]를 i개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값으로 정의할 경우 dp[i]는 모든 조합...
문제 링크 1. 아이디어 MenOfPassion 알고리즘은 $n$에 대해 배열에서 1부터 $n$까지 반복하는 반복문이 중첩된 형태이다. 따라서 코드1의 수행 횟수는 $n^2$번이 되며, 시간 복잡도는 $O(n^2)$이라서 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 2가 된다. 2. 복잡도 접근 ...
문제 링크 1. 아이디어 MenOfPassion 알고리즘은 $n$에 대해 배열에서 1부터 $n$까지 반복하는 반복문이 있는 형태이다. 따라서 코드1의 수행 횟수는 $n$번이 되며, 시간 복잡도는 $O(n)$이라서 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 1이 된다. 2. 복잡도 접근 ...
문제 링크 1. 아이디어 $N$개의 외나무다리에서 흰 왕과 검은 왕이 번갈아 자기 돌을 움직이며, 움직일 수 없는 왕이 지는 게임의 승자를 구하는 문제로 스프라그 그런디 정리를 활용한다. 한 다리에서 두 돌 사이의 빈 칸 수를 더미의 돌 개수로 보면, 자기 돌을 상대 쪽으로 움직이는 것은 그 더미에서 돌을 하나 이상 제거하는 것과 같고 두 돌...
문제 링크 1. 아이디어 볼록 다각형의 두 꼭짓점을 잇는 선분을 서로 교차하지 않게 번갈아 그으며, 더 이상 그을 수 없는 사람이 지는 게임에서 승자를 구하는 문제로 스프라그 그런디 정리를 활용한다. 선분을 하나 그으면 그 두 끝점은 이후 다른 선분과 끝점에서도 겹칠 수 없으므로 막히고, 나머지 점은 선분의 양쪽에 $a$개와 $n - 2 - ...
문제 링크 1. 아이디어 님 게임에서 돌 더미 하나를 비어 있지 않은 두 더미로 나누는 이동이 추가된 문제로, 더미마다 그런디 수를 구해 XOR하는 스프라그 그런디 정리로 해결한다. 돌이 $n$개인 더미의 그런디 수를 $g(n)$이라 하면 돌을 제거하는 이동은 항상 가능하므로 $g(0)$부터 $g(n - 1)$까지로 갈 수 있고, 더미를 $a...
문제 링크 1. 아이디어 각 차례에 1개, $K$개, $K^2$개, …의 금화를 가져갈 수 있을 때, 선공이 이기기 위해 첫 차례에 가져가야 하는 금화 수의 최솟값(이길 수 없으면 0)을 구하는 문제다. $K$가 홀수이면 $K$의 거듭제곱이 모두 홀수라서 한 번 가져갈 때마다 남은 금화의 홀짝이 바뀌므로, 처음 금화가 홀수 개이면 선공이 매번...
문제 링크 1. 아이디어 님 게임에서 선공이 이기기 위해 첫 턴에 할 수 있는 방법의 수를 구하는 문제다. 선공이 이기려면 후공에게 Nim-Sum이 0인 상태를 넘겨야 하므로 첫 턴에 Nim-Sum을 0으로 만드는 수를 세면 된다. 전체 Nim-Sum을 $\text{nim} = p_1 \oplus p_2 \oplus \dots \oplus p...
문제 링크 1. 아이디어 돌 더미에서 피보나치 수만큼만 돌을 제거할 수 있는 님 게임인 핌버에서 승자를 구하는 문제다. 더미는 서로 독립이므로 더미마다 그런디 수를 구해 XOR하는 스프라그 그런디 정리를 쓰며, XOR한 값이 0이 아니면 선공이 이긴다. 돌이 $i$개인 더미의 그런디 수 $g(i)$는 피보나치 수 $f$만큼 제거해 도달하는 $...