동적계획법(Dynamic Programming)

도둑질

1차 시도

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    vector<int> money_reverse(money.rbegin(), money.rend());
    int forward = 0, reverse = 0;

    for (int i=0; i<money.size()-1; i += 2) {
        int now_choice = money[i] - (money[(i-1+money.size())%money.size()] + money[(i+1)%money.size()]);
        int next_choice = money[i+1] - (money[i] + money[(i+2)%money.size()]);
        
        if (now_choice > next_choice) {
            if (i==0) money.back() = 0;
            forward += money[i];
        } else {
            if (i==0) money.push_back(0);
            forward += money[i+1];
            i++;
        }
    } 
    
    for (int i=0; i<money_reverse.size()-1; i += 2) {
        int now_choice = money_reverse[i] - (money_reverse[(i-1+money_reverse.size())%money_reverse.size()] + money_reverse[(i+1)%money_reverse.size()]);
        int next_choice = money_reverse[i+1] - (money_reverse[i] + money_reverse[(i+2)%money_reverse.size()]);
        
        if (now_choice > next_choice) {
            if (i==0) money_reverse.back() = 0;
            reverse += money_reverse[i];
        } else {
            if (i==0) money_reverse.push_back(0);
            reverse += money_reverse[i+1];
            i++;
        }
    } 
    
    return (forward > reverse) ? forward : reverse;
}

정확성  테스트
  테스트 1 〉	실패 (0.02ms, 3.94MB)
  테스트 2 〉	실패 (0.04ms, 3.75MB)
  테스트 3 〉	실패 (0.02ms, 3.95MB)
  테스트 4 〉	실패 (0.01ms, 3.95MB)
  테스트 5 〉	실패 (0.01ms, 3.96MB)
  테스트 6 〉	실패 (0.03ms, 3.95MB)
  테스트 7 〉	실패 (0.02ms, 3.96MB)
  테스트 8 〉	실패 (0.01ms, 3.93MB)
  테스트 9 〉	실패 (0.06ms, 3.94MB)
  테스트 10 〉	실패 (0.01ms, 3.93MB)

효율성  테스트
  테스트 1 〉	실패 (25.73ms, 40.6MB)
  테스트 2 〉	실패 (24.14ms, 38.2MB)
  테스트 3 〉	실패 (26.67ms, 39.6MB)
  테스트 4 〉	실패 (38.17ms, 40MB)
  테스트 5 〉	실패 (22.08ms, 33.6MB)
  테스트 6 〉	실패 (25.48ms, 38.5MB)
  테스트 7 〉	실패 (13.05ms, 22MB)
  테스트 8 〉	실패 (15.51ms, 24.5MB)
  테스트 9 〉	실패 (16.73ms, 28.2MB)
  테스트 10 〉	실패 (26.07ms, 38.8MB)

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

테스트 1
  입력값 〉	[1, 2, 3, 1]
  기댓값 〉	4
  실행 결과 〉	테스트를 통과하였습니다.
테스트 2
  입력값 〉	[90, 0, 0, 95, 1, 1]
  기댓값 〉	185
  실행 결과 〉	테스트를 통과하였습니다.
테스트 3
  입력값 〉	[91, 90, 5, 7, 5, 7]
  기댓값 〉	104
  실행 결과 〉	테스트를 통과하였습니다.
테스트 4
  입력값 〉	[90, 0, 0, 95, 1, 1]
  기댓값 〉	185
  실행 결과 〉	테스트를 통과하였습니다.
테스트 5
  입력값 〉	[91, 90, 5, 7, 5, 7]
  기댓값 〉	104
  실행 결과 〉	테스트를 통과하였습니다.
테스트 6
  입력값 〉	[1, 2, 3]
  기댓값 〉	3
  실행 결과 〉	테스트를 통과하였습니다.
테스트 7
  입력값 〉	[11, 0, 2, 5, 100, 100, 85, 1]
  기댓값 〉	198
  실행 결과 〉	테스트를 통과하였습니다.
테스트 8
  입력값 〉	[0, 0, 0, 0, 100, 0, 0, 100, 0, 0, 1, 1]
  기댓값 〉	201
  실행 결과 〉	테스트를 통과하였습니다.
테스트 9
  입력값 〉	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  기댓값 〉	30
  실행 결과 〉	테스트를 통과하였습니다.
테스트 10
  입력값 〉	[1000, 0, 0, 0, 0, 1000, 0, 0, 0, 0, 0, 1000]
  기댓값 〉	2000
  실행 결과 〉	테스트를 통과하였습니다.
테스트 11
  입력값 〉	[1000, 1, 0, 1, 2, 1000, 0]
  기댓값 〉	2001
  실행 결과 〉	테스트를 통과하였습니다.
테스트 12
  입력값 〉	[1000, 0, 0, 1000, 0, 0, 1000, 0, 0, 1000]
  기댓값 〉	3000
  실행 결과 〉	테스트를 통과하였습니다.
테스트 13
  입력값 〉	[1, 1, 4, 1, 4]
  기댓값 〉	8
  실행 결과 〉	테스트를 통과하였습니다.

테스트 결과 (~˘▾˘)~
  13개 중 13개 성공

2차 시도

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    vector <int> stolen_first_house = {money[0], money[0]};
    vector <int> stolen_second_house = {0, money[1]};

    for (int i=2; i<money.size()-1; i++) {
        if (stolen_first_house[i-2] + money[i] > stolen_first_house[i-1]) {
            stolen_first_house.push_back(stolen_first_house[i-2] + money[i]);
        } else {
            stolen_first_house.push_back(stolen_first_house[i-1]);
        }
    }

    for (int i=2; i<money.size(); i++) {
        if (stolen_second_house[i-2] + money[i] > stolen_second_house[i-1]) {
            stolen_second_house.push_back(stolen_second_house[i-2] + money[i]);
        } else {
            stolen_second_house.push_back(stolen_second_house[i-1]);
        }
    }
     
    return (stolen_first_house[money.size()-2] > stolen_second_house[money.size()-1]) ? stolen_first_house[money.size()-2] : stolen_second_house[money.size()-1];
}

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

효율성  테스트
  테스트 1 〉	통과 (16.82ms, 43MB)
  테스트 2 〉	통과 (15.77ms, 40.7MB)
  테스트 3 〉	통과 (16.89ms, 42.2MB)
  테스트 4 〉	통과 (17.35ms, 42.6MB)
  테스트 5 〉	통과 (14.33ms, 36.9MB)
  테스트 6 〉	통과 (15.50ms, 41.2MB)
  테스트 7 〉	통과 (9.06ms, 24.9MB)
  테스트 8 〉	통과 (9.04ms, 25.6MB)
  테스트 9 〉	통과 (12.94ms, 31.8MB)
  테스트 10 〉	통과 (16.32ms, 41.6MB)

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

깊이/너비 우선 탐색(DFS/BFS)

타겟 넘버

1차 시도

#include <string>
#include <vector>

using namespace std;

int DFS(vector<int> numbers, int target, int now_number, int depth) {
    if (depth == numbers.size()) {
        return (now_number == target) ? true : false;
    }
    
    int plus = DFS(numbers, target, now_number + numbers[depth], depth + 1);
    int minus = DFS(numbers, target, now_number - numbers[depth], depth + 1);
    
    return plus + minus;
}

int solution(vector<int> numbers, int target) {
    return DFS(numbers, target, 0, 0);
}

정확성  테스트
  테스트 1 〉	통과 (65.63ms, 3.82MB)
  테스트 2 〉	통과 (69.89ms, 3.97MB)
  테스트 3 〉	통과 (0.08ms, 3.93MB)
  테스트 4 〉	통과 (0.31ms, 3.96MB)
  테스트 5 〉	통과 (2.23ms, 3.96MB)
  테스트 6 〉	통과 (0.16ms, 3.94MB)
  테스트 7 〉	통과 (0.08ms, 3.94MB)
  테스트 8 〉	통과 (0.64ms, 3.95MB)

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