야 너두 영어로 코딩인터뷰 볼 수 있어! (BOJ 6236 용돈 관리)

어느 날 영어로 진행되는 어떠한 행사에 갔다가

언젠가 중요한 일이 있을 때 영어 때문에 그 기회를 살리지 못하는 일이 없도록 대비해야겠다,

를 온몸으로 실감하여

Sogang ICPC Team에서 영어 스터디를 만들었고 지금 진행 중이다.

가입 관심 있는 분은 연락해 주세요!

학회원 아니어도 괜찮습니다.

서로 모르는 사이여도 괜찮습니다. 알아가면 되죠!

 

어제 2학기 OT에서도 홍보 부탁드려서 슬라이드에 넣었다.

ㅋㅋ

감사합니다!

 

오늘 재미있는 문제를 풀었는데

https://www.acmicpc.net/problem/6236

6236번: 용돈 관리

처음에는 감을 못 잡았는데

브루트포스로 접근하라는 힌트를 줘서 가능한 범위에서 binary search 하는 얘기를 했고 정말 맞았다.

 

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<int> arr(n);
    int sum = 0;

    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        sum += arr[i];
    }

    int left = *max_element(arr.begin(), arr.end()), right = sum + 1;
    int ans = left;
    while (left < right) {
        int mid = (left + right) / 2;
        bool possible = true;
        int n_borrow = 0;
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            if (cur < arr[i]) {
                ++n_borrow;
                cur = mid;
                if (n_borrow > m) {
                    possible = false;
                    break;
                }
            }
            cur -= arr[i];
        }
        if (!possible) {
            left = mid + 1;
        }
        else {
            ans = mid;
            right = mid;
        }
    }

    cout << ans << kEndl;
}

특정한 범위 내에서 조건을 만족하는 수를 찾는다 -> 이분탐색

이라는 기본 원리에 입각한 거였다.

캬

클래식은 영원하다.

감동적이었다.

 

+) 스터디 당시에는 놓쳤는데, k가 될 수 있는 최솟값은 (binary search의 시작 left 값은) input array에서의 최댓값이다. 어쨌든 k원을 인출한 후에 하루를 보낼 수 있으려면 최소한 array의 값들보다는 커야 함.

+) 정말 오랜만에 문제를 맞히는 경험을 했다.

요즘은 알고리즘 문제 풀이를 많이 안 해서 최근에 이런 적이 거의 없었는데.

오랜만에 기분 좋았다.

 

 

 

 

 

 

https://blog.naver.com/mini_gb/223203537811

야 너두 영어로 코딩인터뷰 볼 수 있어! (BOJ 6236 용돈 관리)