[백준 - 16765번] Teamwork - Java //Wello Horld//

이번에는 BOJ의 16765번 문제 "Teamwork" 를 풀어보도록 하자

영어 지문을 간단히 해석해보면, 농사꾼 존씨가 친구들을 위해 선물을 보내려고 한다. 그는 선물 포장을 못하기 때문에 소에게 도움을 청했다. 소들은 일렬로 서있고, 1부터 N까지 편리하게 순서대로 번호가 매겨진다. 소 i는 선물포장 스킬레벨 si를 가지고 있다. 이 스킬레벨은 약간 다를 수 있기에 그의 소들을 팀으로 묶으려 한다. 팀은 최대 K만큼으로 묶여질 수 있으며, 한가지 이상의 팀에 속할 수 없다. 소들은 서로에게 포장기술을 배울 수 있기 때문에, 팀의 각 소의 기술 수준은 해당 팀에서 가장 숙련 된 소의 기술 수준으로 대체 될 수 있다.

입력으로 첫째줄에 N과 K가 주어지고, 그 다음 N줄동안 순서대로 각소의 스킬레벨이 주어진다. 

출력으로 스킬레벨의 총 합이 가장 클 때의 값을 구하면 된다.

반속문을 한번은 N만큼, 한번은 K만큼 돌려서, 최대 값을 구하면 되는 간단한 문제이다.

성공한 코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] level = new int[N];
        for (int i = 0; i < N; i++) {
            level[i] = Integer.parseInt(br.readLine());
        }
        int[] dp = new int[N + 1];
        for(int i = 0; i < N; i++){
            int max = 0;
            for(int j = 0; j < K; j++){
                if(i >= j){
                    if(level[i - j] > max) max = level[i - j];
                    dp[i + 1] = Math.max(dp[i + 1], dp[i - j] + max * (j + 1));
                }
            }
        }
        bw.write(dp[N] + "\n");

        bw.flush();
        br.close();
        bw.close();
    }
}

 

문제 : https://www.acmicpc.net/problem/16765

16765번: Teamwork

 

혹시 코드에 이상한 부분이나 틀린 부분이 있던지, 이해가 안가는 부분이 있다면 댓글로 알려주세요.