• 푸는데 3시간 걸렸다. 
  • 문제를 잘못읽어서 
  • 제대로 읽고 20분 정도만에 fail 코드를 작성했는데 도저히 
정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.
  • 이 경우를 처리할 방법을 모르겠었다. 


  • 좀 더 보니까 알겠다 저 fail 코드에 제일 아래에 쓴 코드 로 바꾸면 된다. 바보다 위는 고려안해도 되네

  • 이 분의 코드는 저런 걸 다르게 언더플로우 걱정없이 할 수 있게 쓰는 코드라고 배울 수 있을 것 같다. 




#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef int ll;
ll tb1[100001];
int n, m;
// ll go(ll nn){ fail
//     ll cnt = 1;
//     int account = nn;
//     for(int i=0;i<n;++i){
//            if(account - tb1[i] >= 0){
//                   account -= tb1[i];
//            }
//            else{
//                   cnt++;
//                   account = nn;
//            }
//     }
//     return cnt;
// }
ll go(ll nn) {
       ll cnt = 1;
       int account = 0;
       for (int i = 0; i<n; ++i) {
              if (account + tb1[i] > nn) {
                     cnt++;
                     account = tb1[i];
              }
              else {
                     account += tb1[i];
              }
       }
       return cnt;
}
int main(void) {
       ll sum = 0, maxv = 0;
       cin >> n >> m;
       for (int i = 0; i<n; ++i) {
              cin >> tb1[i];
              maxv = max(maxv, tb1[i]);
       }
       ll left = maxv;
       ll right = 1987654321; // large value
       while (left <= right) {
              ll mid = (left + right) / 2; // mid는 정한 가격
                                                               //cout << mid << endl;
              int tempv = go(mid);
              if (tempv > m) {
                     left = mid + 1;
              }
              else {
                     right = mid - 1;
              }
       }
       cout << left << endl;
       return 0;
}



// ll go(ll nn){ 
//     ll cnt = 1;
//     int account = nn;
//     for(int i=0;i<n;++i){
//            if(account - tb1[i] >= 0){
//                   account -= tb1[i];
//            }
//            else{
//                   cnt++;
//                   account = nn - tb1[i];
//            }
//     }
//     return cnt;
// }



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

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

[BS] 백준 2792 보석 상자  (0) 2018.04.29
[BS] 백준 1477 휴게소 세우기  (0) 2018.04.29
[BS] 백준 2343 기타레슨  (0) 2018.04.29
[BF] 완전탐색 1018 체스판 다시 칠하기  (0) 2018.04.29
[BF] 백준 2775 부녀회장이 될 테야  (0) 2018.04.29

  • left를 maxv로 하지 않고 1로하면 에러가 난다.
  • 문제만 읽고서는 maxv를 반드시 사용해야할 필요는 모르겠는데 이로인해 에러가 난다. 
#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;
int tb1[100001];
int sum = 0;
int n, m;
int maxv = 0;
//int maxidx;
int go(int k) {
       int temp = k;
       int cnt = 1;
       for (int i = 0; i < n; ++i) {
              int noo = temp - tb1[i];
              if (noo >= 0) {
                     temp = noo;
              }
              else {
                     temp = k - tb1[i];
                     cnt++;
              }
       }
       return cnt;
}
int main(void) {
       
       cin >> n >> m;
       for (int i = 0; i < n; ++i) {
              cin >> tb1[i];
              sum += tb1[i];
              maxv = max(maxv, tb1[i]);
       }
       
       int left = maxv;
       int right = sum;
       while (left <= right) {
              int mid = left + (right - left) / 2;
              //cout << mid << endl;
              if (go(mid) > m) {
                     left = mid + 1;
              }
              else {
                     right = mid - 1;
              }
       }
       
       cout << left << endl;
       return 0;
}


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

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

[BS] 백준 1477 휴게소 세우기  (0) 2018.04.29
[BS] 백준 6236 용돈 관리  (0) 2018.04.29
[BF] 완전탐색 1018 체스판 다시 칠하기  (0) 2018.04.29
[BF] 백준 2775 부녀회장이 될 테야  (0) 2018.04.29
[DP] 백준 2631 줄세우기  (0) 2018.04.29

for문 구현
#include <iostream>
#include <algorithm>

using namespace std;

char table[1001][1001];


int find(int starti,int startj)
{
    int cnt = 0;//B start
    int cnt2 = 0;//W start

    for (int i = starti; i < starti+8; ++i) {
        for (int j = startj; j < startj + 8; ++j) {
            if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
                if (table[i][j] == 'W') {
                    cnt++;
                }
            }
            if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
                if (table[i][j] == 'B') {
                    cnt++;
                }
            }
            if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
                if (table[i][j] == 'B') {
                    cnt2++;
                }
            }
            if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
                if (table[i][j] == 'W') {
                    cnt2++;
                }
            }
        }
    }

    return min(cnt, cnt2);
    
}


int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> table[i][j];
        }
    }
    int ret = INT32_MAX;
    for (int i = 0; i < n - 7; ++i) {
        for (int j = 0; j < m - 7; ++j) {
            ret = min(ret,find(i, j));
        }
    }
    cout << ret << endl;
    return 0;
}


재귀로 구현
#include <iostream>
#include <algorithm>

using namespace std;

char table[1001][1001];

int Bfind(int i, int j,int ans,int sti,int stj) {
    //cout << " i : " << i << "j : " << j << " ans : " << ans << " char : " << table[i][j] << '\n';
    if (j == stj+8) {
        return ans;
    }
    if (i == sti+8) {
        return Bfind(i-8,j+1,ans,sti,stj);
    }
    

    if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
        if (table[i][j] == 'W') {
            ans++;
        }
    }

    if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
        if (table[i][j] == 'B') {
            ans++;
        }
    }
    Bfind(i + 1, j, ans,sti,stj);
}

int Wfind(int i, int j, int ans,int sti,int stj) {
    //cout << " i : " << i << "j : " << j << " ans : " << ans << " char : " << table[i][j] << '\n';
    if (j == stj+8) {
        return ans;
    }
    if (i == sti+8) {
        return Wfind(i - 8, j + 1, ans,sti,stj);
    }


    if ((i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0)) {
        if (table[i][j] == 'B') {
            ans++;
        }
    }
    if ((i % 2 != 0 && j % 2 == 0) || (i % 2 == 0 && j % 2 != 0)) {
        if (table[i][j] == 'W') {
            ans++;
        }
    }
    Wfind(i + 1, j, ans,sti,stj);
}

int find(int starti,int startj)
{
    int cnt = 0;//B start
    int cnt2 = 0;//W start
    cnt = Bfind(starti, startj, 0,starti,startj);
    cnt2 = Wfind(starti, startj, 0,starti,startj);

    //cout << cnt << ' ' << cnt2 << endl;
    return min(cnt, cnt2);
    
}


int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> table[i][j];
        }
    }

    int ret = INT32_MAX;
    for (int i = 0; i < n - 7; ++i) {
        for (int j = 0; j < m - 7; ++j) {
            ret = min(ret,find(i, j));
        }
    }
    cout << ret << endl;
    return 0;
}


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

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

[BS] 백준 6236 용돈 관리  (0) 2018.04.29
[BS] 백준 2343 기타레슨  (0) 2018.04.29
[BF] 백준 2775 부녀회장이 될 테야  (0) 2018.04.29
[DP] 백준 2631 줄세우기  (0) 2018.04.29
[DP] 백준 5557 1학년  (0) 2018.04.29

+ Recent posts

티스토리툴바