[DFS] 백준 16987번 계란으로 계란치기 자바(java) 풀이

BOJ 16987번 계란으로 계란치기 문제 자바(java) 풀이

• 랭크 : 실버3
• 백준 16987번 계란으로 계란치기
  
  
  

문제 정리

1. 계란으로 계란을 치는 경우 다음과 같은 점들을 고려한다.
   • 1.1 계란에는 내구도와 무게가 정해져 있다.
   • 1.2 계란으로 서로를 치면 계란의 내구도는 상대 계란의 무게 만큼 깎이게 된다.
   • 1.3 내구도가 0이 되는 순간 계란이 깨진다.
2. 계란을 왼쪽 부터 차례로 들어 한 번씩만 다른 계란을 쳐서 최대한 많은 계란을 깨려고 한다.
3. 계란을 치는 과정은 다음과 같다.
   • 3.1 가장 왼쪽 계란을 든다.
   • 3.2 손에 든 계란으로 깨지지 않은 계란중 하나를 친다. 만약 손에 든 계란이 깨졌거나 깨지지 않은 계란이 없다면 아무일도 하지 않는다.
   • 3.3 최근에 든 계란의 바로 오른쪽 계란을 들고 반복한다.
     
     
     

문제 풀이

1. dfs 방식으로 모든 경우를 따져주어야 합니다.
2. cnt번째 계란으로 다른 계란들을 모두 쳐봅니다(칠 수 있다면)
   칠 수 있다는 것은 같은 계란이 아니고 두 계란 모두 내구성이 0보다 커야 합니다.
   서로 무게 만큼 빼줍니다.
3. 그리고 다시 다음 계란을 집습니다( solve(cnt+1) )
4. 계란을 집었는데 게란이 이미 깨져있는 경우 그냥 다음으로 넘어갑니다.
5. 또는 깰 계란이 없는 경우 flag가 false로 되어있습니다. 이때도 다음 계란으로 넘어갑니다.
   
   
   

문제 풀이

- 실행시간: 248 ms - 메모리: 16492 kb