[Programmers] 1,2,3 떨어트리기

문제 링크는 다음과 같습니다: https://school.programmers.co.kr/learn/courses/30/lessons/150364?language=cpp

프로그래머스

 

트리 내 경로가 각 회차마다 유일하므로 `떨어지는 i 번째 숫자가 최종적으로 도달하는 리프 노드가 사실상 정해져 있다`는 아이디어로 구현하면 되는 알고리즘 문제였습니다.

 

알고리즘은 다음과 같습니다.

1. 각 횟차마다 숫자가 어느 리프 노드에 도착하는지 시뮬레이션으로 모두 미리 구합니다.

1.1 모든 리프 노드를 1로만 채우는 케이스가 최악의 경우이므로 시뮬레이션은 target 배열의 합만큼 돌리면 됩니다.

 

2. 횟차를 거듭하며 target 배열을 만들 수 있는지 확인합니다.

2.1 한 횟차 당 최대 3을 추가할 수 있으므로 해당 시뮬레이션에서 (리프 노드 L이 방문된 횟수) * 3 < target[리프 노드 L의 인덱스] 일 경우 불가능한 케이스

 

3. target 배열을 만들 수 있다면 각 횟차 당 1, 2, 3 중 어떤 숫자를 할당할지 그리디 하게 결정합니다.

3.1 i 번째 횟차가 방문하는 리프 노드가 L일 때 남은 목푯값은 remain[L]이며 앞으로 L이 방문될 횟수를 고려하여 1 ~ 3 중 가장 작은 값부터 할당하여 목표를 맞출 수 있는지 시도

3.2 도중에 할당이 불가능해질 경우 해당 횟차의 시뮬레이션은 불가능하므로 다음 회차 시뮬레이션 진행

3.3 해당 횟차에 target 배열이 만들어졌다면 투여한 숫자들을 결과로 반환

 

4. target 배열의 합만큼 시뮬레이션을 돌려도 target 배열이 만들어지지 않을 경우 불가능한 케이스이므로 {-1} 반환합니다.

 

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~