링크
양궁대회
난이도
- 프로그래머스 난이도 2
- 빠른 손과 두뇌회전이 필요
- 이걸 실전에서 어케 풀었지?
문제요약
- 어피치와 라이언이 양궁대회를 하는데 어피치는 이미 쏨, 라이언이 최대의 점수차로 이기기위해 어떻게 점수를 얻어야 할까
- 0~10점 과녁이 존재
- 해당 점수 과녁에 많이 맞추면 해당 점수를 가져가는 방식
- 최대 점수를 내는 경우가 많으면, 가장 낮은 점수를 많이 맞춘 사람이 승리
접근
- greedy
- 단순하게 10점 과녁부터 시작하여 어피치보다 +1만큼 맞추면 되겠지?
- 이게 정답이라는 보장도, 해보면 정답도 아니다.
- dfs
- 10점 과녁부터 시작하여
점수를 얻는경우,안맞추고 넘기는경우 이 두가지를 분기로 dfs를 진행
- 만약 어피치가 특정 과녁에 3발을 맞췄다면
4발을 맞춘경우, 0발을 맞춘경우로 분기가 되어 탐색이된다.
- 끝에 도달했을때 어피치와 라이언의 점수차이를 최대가 되는 라이언의 경우들에서 가장 낮은 점수에서 많이 맞춘것을 정답으로 한다.
간단 알고리즘
- n, info
- n은 사용한 전체 화살 갯수
- info는 어피치가 맞춘 과녁 정보(0번째 요소는 10점, 1번째 요소는 9점, …)
- dfs
- 결과로는 라이언이 n개의 화살로 할 수 있는 모든 경우를 배열로 return한다.
- [어피치정보 info,남은화살갯수 count,현재과녁 index,쏜결과 check,결과저장 save]을 가지고 진행
- dfs 시작
- 해당 과녁에서 점수를 얻는경우, 해당과녁 점수를 안받는경우로 두가지 경우로 나뉜다.
info[index]+1 < count인 경우
- 해당 과녁의 점수를 얻기위한 화살갯수가 충분함
- check에 info[index]+1을 추가
- count -= (info[index]+1) 로 현재 화살갯수를 소모를 표시
- 그 외
- 점수를 얻기위한 화살의 갯수(info[index]+1)보다 현재 가지고있는 화살(count)이 적으면 해당 점수를 못받는다.
- check에 0을 추가
- index+1하고 다시 dfs진행
- dfs의 끝
- index가 10이 되면 마지막 과녁 index이며 dfs가 종료되는 시점
- 마지막 과녁에서 남은 화살갯수 count를 확인
- save에 check를 추가
- 위에서 만들어진 n개의 화살로 나올수있는 모든 경우인 save들에 대해 점수 차이 를 계산
- save에서 하나의 배열 s를 확인
- i는 0부터 10까지 반복
- s[i]와 info[i]를 비교
- info[i] < s[i] 이면 라이언이 점수를 얻음
- info[i] > s[i] 이면 어피치가 점수를 얻음
- 점수는 10-i로 계산
- 모든 s에 대해 진행
- 점수차가 max값이 되는 s를 maxlist로 따로 저장
- maxlist가 2개이상인 경우
- i는 1부터 maxlist길이-1 까지 반복
- m1 = maxlist[0]
- m2 = maxlist[i]
- j는 10부터 0으로 반복
- m1[j] > m2[j]이면 m1 = m1
- m1[j] < m2[j]이면 m1 = m2
- 위 반복문을 모든 i에 대해 진행하면 정답이 나온다.
- 생각해야 할 예외들
후기
- 문제의 의도에 맞게 빠르게 구현을 하기만 하면 되는 문제
- dfs를 어떻게 사용하느냐에 따라 문제를 빠르게 해결이 될것으로 보임
- 고려해야할 부분이 많이 없어서 완전탐색으로도 큰 시간이 안걸림
- dfs를 자주 구현해봤으면 그렇게 어렵지 않았을 문제