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