-
[백준 - 16765번] Teamwork - Java //Wello Horld//Algorithm/BOJ(Baekjoon Online Judge) 2019. 12. 9. 13:14
이번에는 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
혹시 코드에 이상한 부분이나 틀린 부분이 있던지, 이해가 안가는 부분이 있다면 댓글로 알려주세요.
'Algorithm > BOJ(Baekjoon Online Judge)' 카테고리의 다른 글
[백준 - 10214번] Baseball - Java //Wello Horld// (0) 2019.12.09 [백준 - 10026번] 적록색약 - Java //Wello Horld// (0) 2019.12.09 [백준 - 2897번] 몬스터 트럭 - Java //Wello Horld// (0) 2019.08.14 [백준 - 3059번] 등장하지 않는 문자의 합 - Java //Wello Horld// (0) 2019.08.14 [백준 - 5337번] 웰컴 - Java //Wello Horld// (0) 2019.08.14