[BOJ 11923] PUTOVANJE

난이도

매겨진 난이도: Bronze I

체감 난이도: Bronze I ~ Silver V (+0.5)

 

태그

• Brute Force (브루트 포스)
• Simulation (시뮬레이션)

 

풀이

 

1. 시작하는 위치가 고정된다면, Mislav가 먹게 되는 과일의 개수는?

문제에서 정의된 Mislav의 이동 방식에 따라, 먹을 수 있다면 먹고 이동 / 아니라면 안 먹고 이동을 하게 됩니다.

위 과정을 직접 시뮬레이션하면, 특정 시작점에서 출발할 때 먹게 되는 과일의 개수를 셀 수 있습니다.

 

2. 그럼, (1번 질문의 답)을 가능한 모든 시작점에 대해 돌려준다면?

가능한 모든 시작점을 둘러보면서, 가장 많이 먹게 되는 경우를 찾아주면 됩니다.

시뮬레이션에 최댓값 찾기까지 복잡해보이지만, 배열에서 최댓값 찾기와 비슷하게 할 수 있습니다.

 

시간복잡도는, (가능한 시작점의 개수) × (각 시작점에서 시뮬레이션하는 시간) = \( O(N \times N) = O(N^2) \)이 됩니다.

 

코드

int arr[1020];
 
void Main(){
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    int ans = 0;
    for (int st = 1; st <= n; st++){
        int sum = 0, cnt = 0;
        for (int ed = st; ed <= n; ed++){
            if (sum+arr[ed] <= k){ sum += arr[ed]; cnt += 1; }
        }
        ans = max(ans, cnt);
    }
    cout << ans;
}