[순열, 완전탐색] 백준 16986 인싸들의 가위바위보 자바(java) 풀이

BOJ 16986 인싸들의 가위바위보 자바(java) 풀이

• 랭크 : 골드3
• 백준 16986 인싸들의 가위바위보
  
  
  

문제 정리

1. 모두가 동시에 경기를 진행하는 대신 일대일 경기를 여러 번 진행해 누가 우승했는지 판단한다.
2. 참가자 3명이서 동시에 경기를 진행할 때, 우승자를 정하기 위한 구체적인 방식은 다음과 같다
   2.1 게임 시작전 우승을 위해 필요한 승수와 경기 진행 순서를 미리 합의 한다.
   2.2 두 사람이 무승부가 날 경우 진행 순서상 뒤의 사람이 이긴 것으로 간주한다.
   2.3 이전 경기의 승자와 이전 경기에 참여하지 않은 사람이 경기를 진행해 승자를 결정한다.
   2.4 특정 사람이 미리 합의된 승수를 달성할 때 까지 2.3을 반복한다.
   2.5 합의된 승수를 최초로 달성한 사람이 우승한다.
3. 상대방 두명이 낼 손동작의 순서와 상성표가 주어질때 지우가 모든 손동작을 다르게 내어 우승할 수 있는지 판단하자.
   
   
   

문제 풀이

지우가 낼 수 있는 경우의 수를 순열로 모두 찾아서 확인해주면 됩니다.

1. 상성표를 arr 배열에 저장합니다.
2. player 배열에 가위바위보를 낼 순서를 저장합니다.
   0번: 지우가 낼 순서
   1번: 경희가 낼 순서
   2번: 민호가 낼 순서
3. 순열 함수를 통해 지우가 낼 수 있는 조합을 구합니다.
4. 구해진 순서를 가지고 게임을 진행합니다. 이때 플레이어가 이긴 횟수를 담은 win, 몇 번째를 낼지에 대한 정보를 담는 order 배열을 선언합니다.
5. while문을 돌며 실행하며 지우, 경희, 민호가 K번 이기거나 지우가 N번 다 냈는데도 K번을 다 못이긴 경우 탈출합니다.
   지우가 K번 이겨서 탈출하는 경우는 flag를 true로 바꿔줍니다.
6. player1과 player2가 게임을 진행하며 player1이 이기면 1은 그대로 두고 2를 other player와 바꿔주고 player1과 바뀐 player2가 다음 경기에 진행합니다.
7. 반대로 player1이 지면 player1과 other player를 바꿔줘서 다음에 player2와 other player(새로 바뀐 player1)가 경기할 수 있도록 합니다.
   
   
   

실행 시간 비교

순열을 모두 구한뒤 if(r==N) 안에서 함수를 불러서 실행한 것과 함수를 따로 호출하지 않고 그대로 쓰는 것의 실행시간이 꽤 차이가납니다
왜냐하면 perm 함수의 경우 재귀적으로 호출하기 때문에 함수가 또 있다면 그 것까지 stack에 다 쌓이게 되기 때문에 메모리도 많이 먹습니다.
그래서 일반적으로 재귀 함수안에 함수를 또 쓰는것은 좋지 않다고 합니다.
아래 시간비교 사진입니다!! 위에가 함수로 빼지 않은 경우 아래가 함수로 뺀 경우 실행시간 입니다.

백준 16986번 인싸들의 가위바위보 자바 코드

- 실행시간: 208 ms
- 메모리: 37492 kb