프로그래머스 양궁대회 javascript

Jay·2022년 10월 23일

알고리즘

목록 보기

1/1

문제 url

문제 설명

라이언이 어피치를 가장 큰 점수 차이로 이기기 위해서 화살을 어떤 과녁 점수에 맞춰야 하는지 구해야 한다. 문제를 읽으면 경우의 수를 탐색해서 조건에 맞는 경우의 수를 구하는 문제라는 것을 알 수 있다. 경우의 수를 구하는 문제에서 어떠한 방법이 떠오르지 않는다면 가장 기본적인 완전 탐색을 고려해볼 수 있다.

아이디어

이 문제는 1~10개의 화살을 11개의 구역에 놓는 경우의 수 구하기로 요약할 수 있다.

중복조합

먼저 탐색 방법으로는 중복을 허용하는 중복 조합이 있다. 총 11개의 과녁 점수가 있고, 제한 사항에서 주어지는 화살의 개수는 최대 10개이다.

중복조합을 선택하였을 때의 경우의 수는 184,756으로 저다고 볼 수는 없지만 많다고 볼 수도 없다. 즉 중복조합으로도 충분히 문제를 해결할 수 있다.

다만 문제 설명을 보았을 때 만약 라이언이 점수를 얻고 싶다고 한다면 단 한 발만 더 맞추면 된다고 나와있다. 이러한 설명으로 보아 greedy한 방식을 적용해서 경우의 수를 더 줄일 수 있음을 알 수 있다.

DFS

라이언이 최대 점수 차이로 이기기 위해 선택할 전략은 다음과 같다.

해당 점수에 대한 과녁을 포기하여 화살을 세이브
어피치보다 단 한 발을 더 맞추어 해당 점수를 획득

이러한 과정을 각 케이스에 대한 분기를 나누어 탐색한다고 가정하면 경우의 수는 2048가지가 된다.

중복조합의 경우의 수 184,756과 비교하면 불필요한 탐색을 많이 걸러내었다고 볼 수 있다.

문제 풀이 전략

10점부터 0점 순으로 라이언과 어피치를 비교해 가면서, 라이언이 해당 점수를 이길지, 포기할 지를 결정하며 가능한 경우를 만들어 간다.
이기는 경우에는 화살을 어피치가 맞춘 화살 개수 + 1개 소모하고, 포기하는 경우에는 화살을 쏘지 않는다.
단, 0점에 도달하기 전에 화살을 모두 소진하면 더 이상 쏠 화살이 없으므로 나머지 점수는 쏘지 않은 것으로 한다. 마찬가지로 0점에 도달하였는데 화살이 남아있더라면, 남은 화살을 모두 0점에 쏜다.

전체 코드

function solution(n, info) {
  let maxDiff = 0; //매번 최대 점수차를 갱신하여 가장 큰 점수차의 점수판을 찾는다.
  let ryonInfo = Array(11).fill(0); //찾아냈다면 ryonInfo에 갱신한다.
  
  const shot = (peachScore, ryonScore, count, idx, board) => {
    if(n < count) return
    if(idx > 10){
      let diff = ryonScore - peachScore;
      if(diff > maxDiff){
        board[10] = n - count;
        maxDiff = diff
        ryonInfo = board;
      }
      return;
    }
		//해당 라운드를 라이언이 가져가는 경우
    if(n > count) {
      let board2 = [...board];
      board2[10 - idx] = info[10 - idx] + 1;
      shot(peachScore, ryonScore + idx, count + info[10 - idx] + 1, idx + 1, board2);
    }
    
		//해당 라운드를 라이언이 포기하는 경우
    if(info[10 - idx] > 0){
      shot(peachScore + idx, ryonScore, count, idx + 1, board)
    } else {
      shot(peachScore, ryonScore, count, idx + 1, board)
    }
  }
	//완전탐색 시작
  shot(0, 0, 0, 0, ryonInfo)
  
  if(maxDiff <= 0) return [-1];
  else return ryonInfo;
}

참고

https://tobegood.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-javascript-js-%EC%96%91%EA%B6%81%EB%8C%80%ED%9A%8C
https://yjyoon-dev.github.io/kakao/2022/01/17/kakao-2022-blind-04/
https://www.youtube.com/watch?v=_kZiCr5xtKk

Jay