탐욕법 (Greedy)

체육복

1차 시도

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector <int> have_clothes(n, 1);
    
    for (int n:lost) have_clothes[n]--;
    for (int n:reserve) have_clothes[n]++;
    
    for (int i=0; i<have_clothes.size(); i++) {
        if (have_clothes[i] == 0) {
            if (i > 0 && have_clothes[i-1] == 2) {
                have_clothes[i-1]--;
                have_clothes[i]++;
            } else if (i < have_clothes.size()-1 && have_clothes[i+1] == 2) {
                have_clothes[i+1]--;
                have_clothes[i]++;
            }
        }
        
        if (have_clothes[i] >= 1) answer++;
    }
    
    return answer;
}

정확성  테스트
  테스트 1 〉	실패 (0.01ms, 3.85MB)
  테스트 2 〉	실패 (0.01ms, 3.97MB)
  테스트 3 〉	통과 (0.01ms, 3.95MB)
  테스트 4 〉	통과 (0.01ms, 3.96MB)
  테스트 5 〉	실패 (0.01ms, 3.95MB)
  테스트 6 〉	통과 (0.01ms, 3.91MB)
  테스트 7 〉	통과 (0.01ms, 3.97MB)
  테스트 8 〉	통과 (0.01ms, 3.96MB)
  테스트 9 〉	실패 (0.01ms, 3.72MB)
  테스트 10 〉	통과 (0.01ms, 3.96MB)
  테스트 11 〉	실패 (0.01ms, 3.89MB)
  테스트 12 〉	통과 (0.01ms, 3.91MB)

채점 결과
  정확성: 58.3
  합계: 58.3 / 100.0

2차 시도

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector <int> have_clothes(n, 1);
    
    for (int n:lost) have_clothes[n-1]--;
    for (int n:reserve) have_clothes[n-1]++;
    
    for (int i=0; i<have_clothes.size(); i++) {
        if (have_clothes[i] == 0) {
            if (i > 0 && have_clothes[i-1] == 2) {
                have_clothes[i-1]--;
                have_clothes[i]++;
            } else if (i < have_clothes.size()-1 && have_clothes[i+1] == 2) {
                have_clothes[i+1]--;
                have_clothes[i]++;
            }
        }
        
        if (have_clothes[i] >= 1) answer++;
    }
    
    return answer;
}

정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.97MB)
  테스트 2 〉	통과 (0.01ms, 3.97MB)
  테스트 3 〉	통과 (0.01ms, 3.78MB)
  테스트 4 〉	통과 (0.01ms, 3.93MB)
  테스트 5 〉	통과 (0.01ms, 3.97MB)
  테스트 6 〉	통과 (0.01ms, 3.82MB)
  테스트 7 〉	통과 (0.01ms, 3.8MB)
  테스트 8 〉	통과 (0.01ms, 3.97MB)
  테스트 9 〉	통과 (0.01ms, 3.91MB)
  테스트 10 〉	통과 (0.01ms, 3.97MB)
  테스트 11 〉	통과 (0.01ms, 3.99MB)
  테스트 12 〉	통과 (0.01ms, 3.92MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0

조이스틱

1차 시도

#include <string>
#include <vector>

using namespace std;

int optimal_distance(string name, int * pos) {
    int left_move = 0, right_move = 0;
    
    for (int i=0; i<name.length(); i++) {
        if ((name[*pos] != 'A') || (left_move != 0 && right_move != 0)) break;

        if (left_move == 0 && name[(*pos - i + name.length()) %  name.length()] != 'A') left_move = i;
        if (right_move == 0 && name[(*pos + i) %  name.length()] != 'A') right_move = i;
    }

    *pos = (*pos + ((left_move < right_move) ? name.length()-left_move : right_move)) % name.length();

    return (left_move < right_move) ? left_move : right_move;
}

int solution(string name) {
    int answer = 0;
    int pos = 0;
     
    vector <int> alphabet_code = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    
    for (string c(name.length(), 'A'); c != name; name[pos] = 'A') {
        answer += optimal_distance(name, &pos) + alphabet_code[name[pos] - 'A'];
    }
    
    return answer;
}

정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.93MB)
  테스트 2 〉	통과 (0.01ms, 3.95MB)
  테스트 3 〉	통과 (0.01ms, 3.95MB)
  테스트 4 〉	통과 (0.01ms, 3.89MB)
  테스트 5 〉	통과 (0.01ms, 3.95MB)
  테스트 6 〉	통과 (0.01ms, 3.95MB)
  테스트 7 〉	통과 (0.01ms, 3.97MB)
  테스트 8 〉	통과 (0.01ms, 3.93MB)
  테스트 9 〉	통과 (0.01ms, 3.89MB)
  테스트 10 〉	통과 (0.01ms, 3.96MB)
  테스트 11 〉	통과 (0.01ms, 3.95MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0