이번문제는 완전탐색으로 풀수있는 문제였다.
핵심을 알면 쉬웠던 문제로, 만약 10점에서 이길꺼면 어피치보다 딱 1발 더쏴서 이기고 질꺼면 아에 안쏘는게 이득이다.
한번 풀어보자.
일단 어떤식으로 접근해야할까?
문제를 처음 볼때 쓱 보면서 이해를 하고 뒤에 이어지는 제한조건을 보면서 n값을 본다.
제한조건인 n이 10발이하이고, 점수대는 0점~11점으로 고정이다.
이렇게 n값이 너무 이상하지 않으면, 일단 시간복잡도를 고려하지 않고, 어떻게 풀지 로직을 짠다.
그 다음에 대충 대충 로직을 짜면 그 로직에 제한조건을 대입했을때 가능한지 확인해보는거다.
라이언입장에서 봐보자, 일단 라이언 입장에서는 점수대마다 이기거나 지는경우밖에 없다. 왜냐하면 어피치와 같은 화살을 쐈으면 어피치가 점수를 가져가기 때문이다.
그러면 0점부터 10점까지 경우의수는 각 점수당 이기거나 지는 경우이므로 2^11일것이다. 이러면 2048인데 여기서 하나의 lose...lose 의 벡터에서 for문으로 각 점수대마다 돌아야하니까 11번을 돌더라도
2^11 곱하기 11 곱하기 3 니까 1억번이내에 돌수있겠다 생각하고 완탐으로 풀어도 되겠다고 생각하는것이다.
그니까 대충 로직을 생각해보고 n값을 대입해서 시간복잡도안에 해결할 수 있는지 파악하라는것이다. 만약에 로직대로했는데 값이 너무 크면 다른방법을 생각해야한다.
어쨋든 그러면 경우의 수는
ffff..f
ffff..t
fffff.tf
등 2^11의 경우를 먼저 만들어야한다.
필자는 Backtracking방법으로 만들었다.
경우의수만들기
vecotr<int>v;
void BT() {
if (v.size() == 10) {
mycheck();
return;
}
for (int j = 0; j < 2; j++) {
if (j == 0) {
v.push_back(0);
BT();
v.pop_back();
}
else {
v.push_back(1);
BT();
v.pop_back();
}
}
}그다음에 size가 10이면 mycheck를 통해서 확인한다.
근데 왜 점수는 11개인데 size가 10일까 바로
vector v는
0번 index부터
10점 9점...순으로 이어지니까 마지막은 index9번에 1점이다.
0점은 누가 이기던지 상관없이 점수가 늘어나지 않으므로 1점까지만센다.->이렇게하면 경우의 수가 최소 1048개는 줄어듬
mycheck
void mycheck() {
int arrow = 0;
int r_score = 0;
vector<int>shoot;
int a_score = 0;
for (int i = 0; i < 10; i++) {
if (v[i]) {
arrow += (info[i] + 1);
shoot.push_back(info[i] + 1);
}
else {
shoot.push_back(0);
}
}
,,,for문으로 v를 돌면서 이기면 arrow에다가 어피치가 쏜 화살수보다 1더해서 더하고, shoot 즉 내가 쏜 화살인 vector에다가 넣는다.
만약 지는경우면 아에 쏘지 않는다.
이렇게 해야하는 이유는 10점에 3발쏜다고 30점을 얻는게아니라 몇발을 쏘든 어피치보다 많이 쏘면 딱 10점만 얻어가는구조이기 때문이다.
그렇다면 질꺼면 아에 안쏘는게 맞다.
왜냐하면 낮은점수에 많이 쏜 답을 return해야하므로 화살이 남으면
남은 화살을 모두 0점에 박으면 되기 때문이다.
//라이언 어피치 점수계산
for (int i = 0; i < 10; i++) {
if (info[i] < shoot[i]) {
r_score += (10 - i);
}
else if (info[i] > shoot[i]) {
a_score += (10 - i);
}
else if (info[i] == shoot[i] && info[i] != 0) {
a_score += (10 - i);
}
}그 다음에 이제 info와 shoot을 바탕으로 점수계산을해준다.
//0점에다 남은 화살 전부 박기
if (r_score > a_score && arrow <= n) {
shoot.push_back(n - arrow);
if(mymax<r_score-a_score){
answer.clear();
answer=shoot;
mymax = r_score-a_score;
}else if(mymax==r_score-a_score){
for (int i = 10; i >= 0; i--) {
if ((shoot[i]>0 || answer[i]>0) && shoot[i] > answer[i]) {
answer.clear();
answer = shoot;
break;
}
else if ((shoot[i] > 0 || answer[i] > 0) && shoot[i] < answer[i]) {
break;
}
}
}
}
}그다음 마지막로직인데 ryan의 점수가 appeach의 점수보다 높은데
화살을 n개 범위내에 쐈다면,
마지막인 0점에다가 남은 화살을 박는게 이득이니까 shoot.push_back(n - arrow); 이렇게 값을 넣어준다.
그다음 최대 점수차이로 이기는게 답이니까 최대 점수차이인지 확인하고
만약, 최대 점수차이라면,
for문을 돌면서 낮은점수에서 answer보다 많이 쐈다면 answer를 갱신해준다.
여기서 핵심은 vector의 index 0 번은 점수로는 10점이므로
거꾸로 0점에 해당하는 index 10부터 확인해야한다는것이다.
정답코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int>v;
vector<int> answer;
vector<int> info;
int n;
int mymax = 0;
void mycheck() {
int arrow = 0;
int r_score = 0;
vector<int>shoot;
int a_score = 0;
for (int i = 0; i < 10; i++) {
if (v[i]) {
arrow += (info[i] + 1);
shoot.push_back(info[i] + 1);
}
else {
shoot.push_back(0);
}
}
//라이언 어피치 점수계산
for (int i = 0; i < 10; i++) {
if (info[i] < shoot[i]) {
r_score += (10 - i);
}
else if (info[i] > shoot[i]) {
a_score += (10 - i);
}
else if (info[i] == shoot[i] && info[i] != 0) {
a_score += (10 - i);
}
}
//0점에다 남은 화살 전부 박기
if (r_score > a_score && arrow <= n) {
shoot.push_back(n - arrow);
if(mymax<r_score-a_score){
answer.clear();
answer=shoot;
mymax = r_score-a_score;
}else if(mymax==r_score-a_score){
for (int i = 10; i >= 0; i--) {
if ((shoot[i]>0 || answer[i]>0) && shoot[i] > answer[i]) {
answer.clear();
answer = shoot;
break;
}
else if ((shoot[i] > 0 || answer[i] > 0) && shoot[i] < answer[i]) {
break;
}
}
}
}
}
void BT() {
if (v.size() == 10) {
mycheck();
return;
}
for (int j = 0; j < 2; j++) {
if (j == 0) {
v.push_back(0);
BT();
v.pop_back();
}
else {
v.push_back(1);
BT();
v.pop_back();
}
}
}
vector<int> solution(int N, vector<int> Info) {
n = N;
info = Info;
for (int i = 0; i < 11; i++) {
answer.push_back(0);
}
BT();
int c=0;
for(int i=0;i<answer.size();i++){
if(answer[i]==0) c++;
}
if(c==11){
answer.clear();
answer.push_back(-1);
}
return answer;
}
