BoBo World

[BaekJoon] #11328 - Strfry [Java][C++]

문제 링크 1. 아이디어 strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어내는 함수로 1번째 문자열에 대해 2번째 문자열이 strfry 함수를 통해 얻어질 수 있으려면 두 단어가 애너그램 관계에 있으면 된다. 따라서 카운팅 배열을 활용해서 1번째 단어의 문자를 카운팅 배열에 더하고 2번째 단어의 문자를 카운팅 배열...

[BaekJoon] #11052 - 카드 구매하기 [Java][C++]

문제 링크 1. 아이디어 $N$개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구해야 하는 문제로 다이나믹 프로그래밍을 활용하면 해결할 수 있다. i개의 카드가 들어있는 카드팩의 가격을 arr[i]로 정의하고, dp 테이블에서 dp[i]를 i개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값으로 정의할 경우 dp[i]는 모든 조합...

[BaekJoon] #18937 - 왕들의 외나무다리 돌게임 [Java][C++]

문제 링크 1. 아이디어 $N$개의 외나무다리에서 흰 왕과 검은 왕이 번갈아 자기 돌을 움직이며, 움직일 수 없는 왕이 지는 게임의 승자를 구하는 문제로 스프라그 그런디 정리를 활용한다. 한 다리에서 두 돌 사이의 빈 칸 수를 더미의 돌 개수로 보면, 자기 돌을 상대 쪽으로 움직이는 것은 그 더미에서 돌을 하나 이상 제거하는 것과 같고 두 돌...

[BaekJoon] #13034 - 다각형 게임 [Java][C++]

문제 링크 1. 아이디어 볼록 다각형의 두 꼭짓점을 잇는 선분을 서로 교차하지 않게 번갈아 그으며, 더 이상 그을 수 없는 사람이 지는 게임에서 승자를 구하는 문제로 스프라그 그런디 정리를 활용한다. 선분을 하나 그으면 그 두 끝점은 이후 다른 선분과 끝점에서도 겹칠 수 없으므로 막히고, 나머지 점은 선분의 양쪽에 $a$개와 $n - 2 - ...

[BaekJoon] #5386 - 금화 게임 [Java][C++]

문제 링크 1. 아이디어 각 차례에 1개, $K$개, $K^2$개, …의 금화를 가져갈 수 있을 때, 선공이 이기기 위해 첫 차례에 가져가야 하는 금화 수의 최솟값(이길 수 없으면 0)을 구하는 문제다. $K$가 홀수이면 $K$의 거듭제곱이 모두 홀수라서 한 번 가져갈 때마다 남은 금화의 홀짝이 바뀌므로, 처음 금화가 홀수 개이면 선공이 매번...

[BaekJoon] #16877 - 핌버 [Java][C++]

문제 링크 1. 아이디어 돌 더미에서 피보나치 수만큼만 돌을 제거할 수 있는 님 게임인 핌버에서 승자를 구하는 문제다. 더미는 서로 독립이므로 더미마다 그런디 수를 구해 XOR하는 스프라그 그런디 정리를 쓰며, XOR한 값이 0이 아니면 선공이 이긴다. 돌이 $i$개인 더미의 그런디 수 $g(i)$는 피보나치 수 $f$만큼 제거해 도달하는 $...