R621(Div.1+Div.2) B. Cow and Friend

ABC중에 제일 어려웠던 문제같다..

 

(0,0) -> (0,x)까지 주어지는 숫자의 길이만큼만 이동해서 가야한다

 

우선 가장 쉬운경우

1. x길이만큼의 수가 주어지는경우 == 1

2. x보다 큰 수가 주어지는 경우 == 2 (삼각형을 만들면 된다)

3. 위에 둘다 아니라면 그 중에 가장 큰걸로 가보면 된다

만약 나머지 수로 x가 나눠떨어진다면 그만큼만 가면 되는거고

조금 더 필요하면 마지막에 삼각형을 만든다는 생각으로 하나 더 쓰면 된다!

 

이런걸 빠르게 생각하는게 아직은 좀 어려운듯 하다! 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int t;
 
int main() {
    scanf(" %d", &t);
    while (t--) {
        int n, m; scanf(" %d %d", &n, &m);
        int maxn = 0; int ans = 1e9;
        for (int i = 0; i < n; i++) {
            int x; scanf(" %d", &x);
            maxn = max(maxn, x);
            if (x == m) ans = min(ans, 1);
            if (x > m) ans = min(ans, 2);
        }
        if (ans == 1e9) {
            int cnt = m / maxn;
            if (m%maxn) cnt += 1;
            ans = min(ans, cnt);
        }
        printf("%d\n", ans);
    }
}