문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/92342?
카카오 코딩테스트로 나오면 문제인데, 자주 풀어보긴 해야겠다.
문제 핵심 및 풀이
해당 문제의 유형은 제한사항을 보면 알 수 있다.
최대 10발까지 가능하고, 점수도 11개가 끝이다.
충분히 완전탐색으로 풀 수 있는 문제다.
라이언 점수 경우의 수
완전 탐색으로 풀면 되기 때문에, 백트래킹을 떠올렸다.
n개의 화살을 11개의 점수에 각각 넣어보면 된다.
여기서 중요한 것은 맞추는 순서는 상관없다는 것이다.
어차피 해당 점수에 맞은 화살 개수만을 따지기 때문에
백트래킹할 때 중복 조합으로 구현해 주면 된다.
점수 계산
점수를 구하는 방법은 간단하다.
모든 점수를 확인해 주면서 어피치와 라이언의 개수를 비교한다.
이때 라이언이 이기는 것이 목표이기 때문에,
개수가 무조건 피치보다 많아야 한다.
그렇게 개수를 세는 행위를 반복하고, 점수를 합한다.
그리고 (라이언 점수) - (어피치 점수)를 통해 격차를 구한다.
실수하기 쉬운 부분
이 문제는 실수가 나오기 쉬운데,
하나는 같은 점수에 맞춘 화살의 개수만큼 점수를 계산하는 것.
문제를 잘못 읽으면 나올 수 있는 실수이다.
중요한 것은 두 번째인데, 여기서는 만약 최종점수가 같을 때는
가장 낮은 점수가 더 많은 것이 답이 된다는 것이다.
그래서 미리 구해놓은 maxScore가 같을 때는
마지막 배열부터 시작하여, 새로 구한 값의 낮은 점수 개수와 비교한다.
이때 실수하기 쉬운 점은
maxScore에 해당하는 배열이 클 경우에도 바로 끝내줘야 한다는 것이다.
해당 부분을 못해서 계속 틀렸다..
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
using namespace std;
void backtracking(int,int); // 함수 정의
void simulation();
int len; // 입력 n
// 각 점수의 정댑 배열을 0으로 초기화
vector<int> peach;
vector<int> answer = {0,0,0,0,0,0,0,0,0,0,0};
vector<int> lion = {0,0,0,0,0,0,0,0,0,0,0};
int maxScore = 0; // 최대점수
// 백트래킹을 통해 나올 수 있는 모든 경우의 수를 구한뒤
// 바로 점수 계산을 시작한다.
void backtracking(int start, int cnt){
if(cnt == len){
simulation();
return;
}
for(int i = start; i <= 10; i++){
lion[i]++;
backtracking(i,cnt+1);
lion[i]--;
}
}
// 점수 계산 함수
void simulation(){
int lScore = 0; // 라이언 점수
int pScore = 0; // 어피치 점수
// 둘 다 0일때를 제외하고는 라이언이 커야지만 점수를 얻는다.
for(int i = 0; i <= 10; i++){
if(lion[i] == 0 && peach[i] == 0) continue;
if(lion[i] > peach[i]) lScore += 10-i;
else pScore += 10-i;
}
int result = lScore - pScore; // 두 사람의 격차
// 라이언이 이기고, 새로운 점수가 기존 점수보다 크거나 같을 때
if(result >= maxScore && lScore > pScore){
// 점수가 같을 때는 제일 낮은 점수의 개수 비교
if(result == maxScore){
for(int i = 10; i >= 0; i--){
if(lion[i] > answer[i]){
answer = lion;
return;
}
// 가장 낮은 점수가 기존의 정답 배열이 더 클 때
else if(lion[i] < answer[i]) return;
}
}
// 새로 구한 최종 점수가 더 클때
else{
answer = lion;
}
maxScore = result; // 점수 갱신
}
}
vector<int> solution(int n, vector<int> info) {
len = n;
peach = info;
backtracking(0,0);
// 최종 점수가 0점이라면 실패
if(maxScore == 0) {
answer.clear();
answer.push_back(-1);
}
return answer;
}↑
Java 구현 코드
↓
import java.util.*;
import java.util.stream.*;
class Solution {
List<Integer> infoList;
static int[] peach; // 전역 변수화를 해줌
// 각 점수의 정답 개수 0으로 초기화
static int[] lion = {0,0,0,0,0,0,0,0,0,0,0};
static int maxScore = 0; // 최대 점수
static int[] answer = {0,0,0,0,0,0,0,0,0,0,0};
// 백트래킹을 통해 구한 경우의 수를 바로 계산한다.
// (start = 중복 조합을 위한 인덱스, cnt = 현재 화살 갯수, size = 화살 총 개수)
void backtracking(int start, int cnt, int size){
// 모든 화살을 다 쏘면 점수 계산 시작
if(cnt >= size){
int pScore = 0; // 라이언 점수
int lScore = 0; // 어피치 점수
// 둘 다 0일때를 제외하고는 라이언이 커야지만 점수를 얻는다.
for(int i = 0; i < peach.length; i++){
if(peach[i] == 0 && lion[i] == 0) continue;
if(lion[i] > peach[i]) lScore += 10-i;
else pScore += 10-i;
}
// 두 사람의 격차 점수
int cntScore = lScore - pScore;
// 일단 라이언이 이겨야함
if(lScore > pScore){
// 기존 점수보다 크면 바로 할당해주면 됨
if(cntScore > maxScore){
maxScore = cntScore;
answer = lion.clone();
}
// 기존 점수와 같을 경우
else if(cntScore == maxScore){
// 마지막 배열부터 앞으로 이동
for(int i = 10; i >= 0; i--){
// 가장 낮은 수가 새로 찾은 배열이 더 클때,
if(lion[i] > answer[i]){
answer = lion.clone();
}
// 가장 낮은 수가 기존의 정답 배열이 클 때
else if(lion[i] < answer[i]) return;
}
}
}
return; // 종료
}
// 중복 조합으로 백트래킹
for(int i = start; i <= 10; i++){
if(lion[i] > peach[i]) continue;
lion[i]++;
backtracking(i,cnt+1,size);
lion[i]--; // 끝나면 다른 경우를 위해 원상복구
}
}
public int[] solution(int n, int[] info) {
peach = info;
backtracking(0,0,n);
// 스트림을 통해 구한 정답 배열의 0 개수가 11개면 실패임
if(Arrays.stream(answer).filter(e -> e == 0).count() == 11)
answer = new int[]{-1};
return answer;
}
}↑
자바를 먼저 풀고 C++로 풀어서 두 코드가 좀 다르다.
하지만 근본적인 부분은 같다.
시행착오
백트래킹으로 푸는 것도 다 알고 다 알았는데...
실수하기 쉬운 부분에서 두 번째 부분을 알지 못했다.
또한 중복 조합을 구현하지 못해서 실패했다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me