λ¬Έμ
λ¬Έμ λ§ν¬ \https://www.acmicpc.net/problem/2579
- κ³λ¨ μ€λ₯΄κΈ° κ²μμ κ³λ¨ μλ μμμ λΆν° κ³λ¨ κΌλκΈ°μ μμΉν λμ°©μ κΉμ§ κ°λ κ²μμ΄λ€. <κ·Έλ¦Ό 1>κ³Ό κ°μ΄ κ°κ°μ κ³λ¨μλ μΌμ ν μ μκ° μ°μ¬ μλλ° κ³λ¨μ λ°μΌλ©΄ κ·Έ κ³λ¨μ μ°μ¬ μλ μ μλ₯Ό μ»κ² λλ€
- μλ₯Ό λ€μ΄ <κ·Έλ¦Ό 2>μ κ°μ΄ μμμ μμλΆν° 첫 λ²μ§Έ, λ λ²μ§Έ, λ€ λ²μ§Έ, μ¬μ― λ²μ§Έ κ³λ¨μ λ°μ λμ°©μ μ λλ¬νλ©΄ μ΄ μ μλ 10 + 20 + 25 + 20 = 75μ μ΄ λλ€.
- κ³λ¨ μ€λ₯΄λ λ°λ λ€μκ³Ό κ°μ κ·μΉμ΄ μλ€.
- κ³λ¨μ ν λ²μ ν κ³λ¨μ© λλ λ κ³λ¨μ© μ€λ₯Ό μ μλ€. μ¦, ν κ³λ¨μ λ°μΌλ©΄μ μ΄μ΄μ λ€μ κ³λ¨μ΄λ, λ€μ λ€μ κ³λ¨μΌλ‘ μ€λ₯Ό μ μλ€.
- μ°μλ μΈ κ°μ κ³λ¨μ λͺ¨λ λ°μμλ μ λλ€. λ¨, μμμ μ κ³λ¨μ ν¬ν¨λμ§ μλλ€.
- λ§μ§λ§ λμ°© κ³λ¨μ λ°λμ λ°μμΌ νλ€.
- λ°λΌμ 첫 λ²μ§Έ κ³λ¨μ λ°κ³ μ΄μ΄ λ λ²μ§Έ κ³λ¨μ΄λ, μΈ λ²μ§Έ κ³λ¨μΌλ‘ μ€λ₯Ό μ μλ€.
- νμ§λ§, 첫 λ²μ§Έ κ³λ¨μ λ°κ³ μ΄μ΄ λ€ λ²μ§Έ κ³λ¨μΌλ‘ μ¬λΌκ°κ±°λ, 첫 λ²μ§Έ, λ λ²μ§Έ, μΈ λ²μ§Έ κ³λ¨μ μ°μν΄μ λͺ¨λ λ°μ μλ μλ€.
- κ° κ³λ¨μ μ°μ¬ μλ μ μκ° μ£Όμ΄μ§ λ μ΄ κ²μμμ μ»μ μ μλ μ΄ μ μμ μ΅λκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
- μ λ ₯μ 첫째 μ€μ κ³λ¨μ κ°μκ° μ£Όμ΄μ§λ€.
- λμ§Έ μ€λΆν° ν μ€μ νλμ© μ μΌ μλμ λμΈ κ³λ¨λΆν° μμλλ‘ κ° κ³λ¨μ μ°μ¬ μλ μ μκ° μ£Όμ΄μ§λ€. κ³λ¨μ κ°μλ 300μ΄νμ μμ°μμ΄κ³ , κ³λ¨μ μ°μ¬ μλ μ μλ 10,000μ΄νμ μμ°μμ΄λ€.
- 첫째 μ€μ κ³λ¨ μ€λ₯΄κΈ° κ²μμμ μ»μ μ μλ μ΄ μ μμ μ΅λκ°μ μΆλ ₯νλ€.
μμ΄λμ΄
- κ³λ¨μ΄ 2κ°μΌλκΉμ§λ λͺ¨λ κ³λ¨κ°μ λν΄μ£Όλ©΄ λλ―λ‘ κ·Έλ κ² μ΄κΈ°κ°μ μ μ₯νλ€.
- κ³λ¨μ΄ 3κ°μΌλλ 1λ² 3λ² κ³λ¨ ν©κ³Ό 2λ² 3λ² κ³λ¨ ν© μ€ μ΄λ€ κ²μ΄ λ ν°μ§ λΉκ΅ν΄μ μ μ₯νλ€.
- κ³λ¨λ€μ μ μ ν©μ λ°°μ΄μ μ μ₯νλλ° λ°°μ΄μ iλ²μ§Έλ iλ²μ§Έ κ³λ¨κΉμ§μ μ΅λκ°μ μλ―Ένλ€.
- κ·Έλ¦¬κ³ λ§μ§λ§ κ³λ¨μ 무쑰건 λ°μμΌ λλ―λ‘ iλ²μ§Έ κ³λ¨μ 무쑰건 ν¬ν¨ν΄μ 4λ²μ§Έ κ³λ¨λΆν° Nκ°μ κ³λ¨κΉμ§ λ°λ³΅νλ€.
- iλ²μ§Έ κ³λ¨κΉμ§μ μ΅λκ°μ ꡬν λ, iλ²μ§Έ κ³λ¨ + (i-1)λ²μ§Έ κ³λ¨μ i-3λ²μ§ΈκΉμ§μ μ΅λκ°μ λν κ°κ³Ό iλ²μ§Έ κ³λ¨ + i-2λ²μ§ΈκΉμ§μ μ΅λκ°μ λν κ° μ€ λ ν° κ°μ μ μ₯νλ€. (μ°μμΌλ‘ 3κ°μ κ³λ¨μ λ°μ μ μμΌλ―λ‘ iλ²μ§Έ κ³λ¨μ κΈ°μ€μΌλ‘ μ°μ λκ°μ κ³λ¨μ λ°μ κ²κ³Ό νκ°μ κ³λ¨μ λ°μ κ²μ λΉκ΅)
κ²ͺμ μνμ°©μ€
- μ΄ λ¬Έμ λ₯Ό μ²μ λ΄€μλ, 'dpλ‘ νμ΄μΌλκ² λ€..!' μκ°μ νκ³ μμ μΈμλ³΄λ €κ³ νμλ€.
- μμ μ΄λμ λ λκ° μΈμ보μμ§λ§, λ§μ§λ§ κ³λ¨μ 무쑰건 λ°μμΌ λλ€λ μ κ³Ό κ³λ¨λ€μ μ μ ν© μ€ μ΅λκ°μ μ΄λ»κ² μ°Ύμ§λΌλ λλ λ§μ λΉ μ§λ©°... λ¬Έμ κ° μνλ Έλ€...
- κ²°κ΅ μ λ§ λ§μ κ³ λ―Όμ νλ€κ° νμ΄λ₯Ό νλ² μ½κ³ λ€μ νκ² λμλ€ γ γ γ
- μ¬λ§νλ©΄ νμ΄λ₯Ό λ³΄μ§ μκ³ λ¬Έμ λ₯Ό νλ €κ³ νμ§λ§... ν΄λΉ λ¬Έμ λ λ°©λ²μ΄ μ λ§ μ λλ‘ μκ°μ΄ λμ§ μμμ μ΄μ© μ μμ΄ λ³΄μλ€...
- κ·Έλλ νμ΄λ³΄κ³ λ€μ νλ©΄μ μ£Όμμ νλνλ μΈμΈνκ² λ¬λ©΄μ μ λλ‘ μ΄ν΄ν΄λ³΄λ €κ³ νλ€.
- μ΄ μ λλ©΄ μ¬μ΄ dpλ¬Έμ μΌν λ° λ²μ¨ μ΄λ €μνλ... μμΌλ‘ λ¨μ dpλ¬Έμ λ€μ΄ κ±±μ λμ§λ§ μ΄λ²κΈ°νμ dpλ₯Ό μ λλ‘ μ΄ν΄ν΄μ λ€μλΆν°λ μ΅λν λ΄ νμΌλ‘ νμ΄μΌκ² λ€..! (ν¬κΈ°νμ§ λ§κΈ°..!!)
μ½λ
import java.util.*;
import java.io.*;
public class BOJ2579 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// κ³λ¨ μ μ μ μ₯ λ°°μ΄
int stairs[] = new int[N + 1];
// κ³λ¨μ μ μλ€μ λν λ°°μ΄
int scores[] = new int[N + 1];
for(int i = 1; i <= N; i++){
int s = Integer.parseInt(br.readLine());
// κ³λ¨ μ μ μ μ₯
stairs[i] = s;
}
// κ³λ¨μ΄ νκ°μΌ λ, κ³λ¨ νκ°μ μ μλ§ λνλ©΄λ¨
if(N == 1){
scores[1] = stairs[1];
}
// κ³λ¨μ΄ λκ°μΌ λ, κ³λ¨ λκ°μ μ μλ§ λνλ©΄λ¨
else if(N == 2){
scores[2] = stairs[1] + stairs[2];
}
// κ³λ¨μ΄ 3κ° μ΄μμΌ κ²½μ°,
else{
// 1λ²μ§Έ κ³λ¨κΉμ§ μ΅κ³ μ μλ 1λ² κ³λ¨ μ μλ§
scores[1] = stairs[1];
// 2λ²μ§Έ κ³λ¨κΉμ§ μ΅κ³ μ μλ 1λ² κ³λ¨ + 2λ² κ³λ¨ μ μ
scores[2] = stairs[1] + stairs[2];
// 3λ²μ§Έ κ³λ¨κΉμ§ μ΅κ³ μ μλ 3κ°μ κ³λ¨μ μ°μν΄μ λ°μΌλ©΄ μλλ―λ‘
// 1λ² + 3λ²κ³Ό 2λ² + 3λ² μ€ λ ν° κ°μΌλ‘ μ μ₯
scores[3] = Math.max(stairs[1] + stairs[3], stairs[2] + stairs[3]);
// 4λ²μ§Έ κ³λ¨λΆν° Nλ²μ§Έ κ³λ¨κΉμ§ λ°λ³΅
for(int i = 4; i < N + 1; i++){
// λμ κ³λ¨μ 무쑰건 λ°μμΌλ¨
// νμ¬ κ³λ¨μ κΈ°μ€μΌλ‘ μ°μ λμΉΈμΌλ‘ λ°μμ§ νμΉΈμΌλ‘ λ°μμ§μ λ°λΌ λΉκ΅
// νμ¬ κ³λ¨μ κΈ°μ€μΌλ‘ μ°μν΄μ λμΉΈμ λ°λλ€λ©΄
// iλ²μ§Έ κ³λ¨ + i-1λ²μ§Έ κ³λ¨μ i-3λ²μ§Έ κ³λ¨κΉμ§μ μ΅λκ°μ λν κ°,
// νμ¬ κ³λ¨μ κΈ°μ€μΌλ‘ μ°μν΄μ νμΉΈμ λ°λλ€λ©΄
// iλ²μ§Έ κ³λ¨ + i-2λ²μ§Έ κ³λ¨κΉμ§μ μ΅λκ°μ λν κ°μ΄ λμ€λλ°
// μ κ°λ€μ λΉκ΅ν΄μ λ ν° κ°μ ν΄λΉ iλ²μ§Έ κ³λ¨κΉμ§μ μ΅λκ°μ μ μ₯
scores[i] = Math.max(scores[i - 3] + stairs[i - 1] + stairs[i], scores[i - 2] + stairs[i]);
}
}
System.out.println(scores[N]);
}
}
'μκ³ λ¦¬μ¦' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Java] BOJ 9095 1, 2, 3 λνκΈ° (0) | 2024.07.28 |
---|---|
[Java] BOJ 2606 λ°μ΄λ¬μ€ (0) | 2024.07.27 |
[Java] BOJ 1463 1λ‘ λ§λ€κΈ° (2) | 2024.07.27 |
[Java] BOJ 1003 νΌλ³΄λμΉ ν¨μ (0) | 2024.07.26 |
[Java] BOJ 17219 λΉλ°λ²νΈ μ°ΎκΈ° (6) | 2024.07.24 |