Neo Ground

13252번: 카지노 아이디어우선 최적의 전략이 무엇인지 알아내는 것이 중요하다.결론부터 말하면, 플레이어들이 영역에 칩을 최대한 고르게 베팅하는 것이 최적의 전략이다.사실 이게 왜 최적의 전략인지는 잘 모르겠다. 대충 맞는 것 같아서 풀었다... 풀다보니 이게 골드가 맞나 싶었다.수학으로 풀리는 건가 싶어 고민해 봐도 도저히 간단한 식으로 유도될 것 같지 않았다. 그러면 DP를 의심해 본다.(N, M, K)의 게임의 확률을 P(N, M, K)라 하면 적당한 p에 대해 (0P(N-(N//M), M, K-1)*p + P(N-(N//M+1), M, K-1)*(1-p)로 계산 된다.이렇게 재귀 DP를 굴리면 될 듯도 하다. 시간이 초과되지 않을까 의심됐지만 다른 방법이 안 떠올라 일단 구현을 했다. 구현위 설..

24526번: 전화 돌리기 아이디어문제를 단방향 그래프로 표현할 수 있다.어떤 부원이 두 번 이상 전화를 받게 되려면, 그 부원이 어떤 사이클에 존재해야 한다.더불어 사이클에 존재하는 부원들에게 전화를 넘겨줄 수 있는 부원들과, 그 부원들에게 넘겨줄 수 있는 또다른 부원들과, ... 재귀적으로 이런 부원들은 잠재적으로 어떤 부원이 두 번 이상 전화를 받게 할 수 있다.반면, 그렇지 않은 부원이 다시 사이클에 진입 시킬 수 없는 부원이고 아래 그래프에서는 6, 7, 8번 정점에 해당한다. 구현6, 7, 8번 정점과 같은 정점을 찾자.DFS와 유사한 방식으로 자식의 리턴값을 이용해서 구현할 수도 있다. 하지만 훨 간단한 방법이 있다.모든 정점의 자식의 수(혹은 out edge의 개수)를 관리한다.자식의 수가..