인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

모든 경우를 생각했을 때 (60,60,60) 에서 계속 (9,3,1)을 빼는게 최악이라 생각했고 이 경우까지 도달하기 위해선

1+6+6^2+..6^60 이라 생각해서 그래프로 풀 생각을 하지 못했습니다.

->

처음에 시간복잡도 판단은 좋았는데요. ㅎㅎ

BFS로 풀게 되면 반복되는 경우의 수를 visited로 걸러내고 해당 부분부터 시작되는 경우의 수가 감소하기 때문에 풀 수 있다고 생각하시면 됩니다.

예를 들어 어쩌다 보니 30, 30, 30 까지 오는 경우의 수가 10개가 존재한다라고 하면 그 다음부터 최대는 10* 6 ... 이런식으로 가게 됩니다. (만약 방문처리를 안하면요.)

하지만 bfs - visited로 방문처리를 하기 때문에 해당 경우의 수는 1개만 존재하게 되어 계산해야 하는 경우의 수가 줄어들게 됩니다.

어차피 우리가 원하는 것은 최솟값인데 예를 들어 해당 경우의 수를 12, 15, 9번만에 방문했을 때 필요한 것은 9번부터 시작되는 경우의 수임이 자명합니다.

만약 각각 9, 9, 9번만에 방문하더라도 방문처리가 되어있으면 이 중 단 한번만 체크하면 되기 때문에 그 이후로부터 경우의 수가 기하급수적으로 증가하지 않게 되는 효과가 있는 것이죠.

이러한 부분들을 생각해서 bfs로 접근하면 되지 않을까? 하고 들어가시면 됩니다.

감사합니다.