BOJ 4994 - 배수 찾기
간만에 본 문제라 생각이 잘 안나서 $dp[m][mod][greater]$ 으로 $m$ 자리수일 때 $n$으로 나눈 나머지가 $mod$이고, $1$을 한 번이라도 썼는지 여부를 $greater$라고 표현할 때 가능한지에 대한 여부로 DP를 돌려주고 역추적해서 풀었다.
정해는 naive하게도 되는 모양이지만,
이 문제는 BOJ 8112 - 0과 1 - 2문제처럼 BFS로 푸는것이 가장 깔끔하다.
큐에 <n으로 나눈 나머지, 문자열> 을 들고다니며 $n$으로 나눈 나머지를 방문했는지 안방문했는지에 대하여 계속해서 큐에 넣어주다 나머지가 0이 되는 시점을 보면 된다.
처음엔 $1$을 넣어주면 된다.
Comments