2 3 5 8 ... 피보나치

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
bool vipsit[41];
long long dp[43];
void cal_part() {
       dp[0] = 1; // 이거 해주는 이유는 vip가 두번 연속 나왔을 때 0
으로 초기화 되어 있으면 값이 0이 되므로 1을 해줘도 전체적인 값에 영향은 없다 .
       dp[1] = 1;     
       dp[2] = 2;
       for (int i = 3; i <= 43; ++i) {
               dp[i] = dp[i-1] + dp[i-2];
       }
}
void print_part() {
       for (int i = 1; i <= 100; ++i) {
               cout << dp[i] << ' ';
       }
       cout << endl;
}
int main(void) {
       int n;
       cin >> n;
       int t;
       cin >> t;
       cal_part();
       //print_part();
       for (int i = 0; i < t; ++i) {
               int k;
               cin >> k;
               vipsit[k] = true;
       }
       int ans = 1;
       int cnt = 0;
       for (int i = 1; i <= n; ++i) {
               if (vipsit[i] == true) {
                      ans *= dp[cnt];
                      cnt = 0;
               }
               else {
                      cnt++;
               }
       }
       if (cnt > 0) {
               ans *= dp[cnt];
       }
       cout << ans << endl;
       return 0;
       
}// 123 4 56 7 89
    // 3 * 2 * 2


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 1495 기타리스트  (0) 2018.04.29
[DP] 백준 2240 자두나무  (0) 2018.04.29
[DP] 백준 1932 숫자삼각형  (0) 2018.04.29
[DP] 백준 14501 퇴사  (0) 2018.04.29
[DP] 백준 1520 내리막길  (0) 2018.04.29


유형은 거의 비슷했고 max안에서 d[i-1][j-1]을 d[i-1][j+1]로 생각해서 조금 해맸었다. 
감으로 하지말고 종이로 생각하면서 하니까 문제점을 찾을 수 있었다. 
메모리랑 시간이 좀 효율적이지 못하다는 것을 보여주는데 나중에 배열을 덜 쓰던가 해서 수정해 보자.

#include <iostream>
#define max(a,b) ((a)>(b) ? (a) : (b))
using namespace std;
int d[501][501];
int sample[501][501];
int main() {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
               for (int j = 1; j <= i; ++j) {
                       cin >> sample[i][j];
               }
        }
        d[1][1] = sample[1][1];
        for (int i = 2; i <= n; ++i) {
               for (int j = 1; j <= i; ++j) {
                       d[i][j] += max((d[i - 1][j] + sample[i][j]), (d[i - 1][j - 1] + sample[i][j]));
               }
        }
        int ans = 0;
        for (int j = 1; j <= n; ++j) {
               if (ans < d[n][j])
                       ans = d[n][j];
        }
        cout << ans;
        return 0;
}



저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 2240 자두나무  (0) 2018.04.29
[DP] 백준 2302 극장 좌석  (0) 2018.04.29
[DP] 백준 14501 퇴사  (0) 2018.04.29
[DP] 백준 1520 내리막길  (0) 2018.04.29
[DP] 백준 9251 LCS  (0) 2018.04.29


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int day[1001];
int val[1001];
int dp[1001];
int n; //n 일까지
int go(int idx) {
       /*cout << idx << endl;*/
       if (idx > n) {
               return 0;
       }
       int& ret = dp[idx];
       if (ret != -1) {
               return ret;
       }
       if (idx + day[idx] <= n+1) { // 8일째에 3일일하라고 하면 10일까지 일하는 거니까 +1을 하던 가 -1을 하던가
               ret = max(go(idx + day[idx]) + val[idx], go(idx + 1));
       }
       else {
               ret = go(idx + 1);
       }
       
       return ret;
}
int main(void) {
       memset(dp, -1, sizeof(dp));
       cin >> n;
       // i 가 의미하는 것 : i일째
       for (int i = 1; i <= n; ++i) {
               cin >> day[i];
               cin >> val[i];
       }// input 끝
       cout << go(1) << endl; //1일차 시작
       /*for (int i = 1; i <= n; ++i) {
               cout << dp[i] << ' ';
       }*/
       return 0;
       
}

저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 2302 극장 좌석  (0) 2018.04.29
[DP] 백준 1932 숫자삼각형  (0) 2018.04.29
[DP] 백준 1520 내리막길  (0) 2018.04.29
[DP] 백준 9251 LCS  (0) 2018.04.29
[DP] 백준 10942 팰린드롬?  (0) 2018.04.29

+ Recent posts

티스토리툴바