문제 출처: https://www.acmicpc.net/problem/1149



세 이웃 간 색깔이 달라야 하는 것이 아니라, 두 이웃 간 색깔이 다르면 된다. (ex: 빨강 초록 빨강)


DP(Dynamic Programming)로 푼다.

cost[0][0] = 26  // 집1을 빨강으로 칠할 때 비용 

cost[0][1] = 40  // 집1을 초록으로 칠할 때 비용 

cost[0][2] = 83  // 집1을 파랑으로 칠할 때 비용 

cost[1][0] = min(cost[0][1], cost[0][2]) + cost[1][0]  // 집1을 초록과 파랑으로 칠할 때 비용 중 최솟값과, 집2를 빨강으로 칠할 때 비용

cost[1][1] = min(cost[0][0], cost[0][2]) + cost[1][1]  // 집1을 빨강과 파랑으로 칠할 때 비용 중 최솟값과, 집2를 초록으로 칠할 때 비용

cost[1][2] = min(cost[0][0], cost[0][1]) + cost[1][2]  // 집1을 빨강과 초록으로 칠할 때 비용 중 최솟값과, 집2를 파랑으로 칠할 때 비용


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[][] cost = new int[N][3];
 
        for(int i=0 ; i<N ; i++){
            String[] input = reader.readLine().split(" ");
            cost[i][0] = Integer.parseInt(input[0]);
            cost[i][1] = Integer.parseInt(input[1]);
            cost[i][2] = Integer.parseInt(input[2]);
        }
 
        for(int i=1 ; i<N ; i++){
        // cost[i][0] = 집 i을 빨강으로 칠할 때 비용 + 집 i-1을 빨강을 제외한 나머지 색들로 칠할 때의 비용 중 최소값
            cost[i][0] += Math.min(cost[i-1][1], cost[i-1][2]); // 49 += (40, 83)
            cost[i][1] += Math.min(cost[i-1][0], cost[i-1][2]); // 60 += (26, 83)
            cost[i][2] += Math.min(cost[i-1][0], cost[i-1][1]); // 57 += (26, 40)
        }
 
        Arrays.sort(cost[N-1]);
        System.out.println(cost[N-1][0]);
    }
}
cs



저작자표시

'Algorithm' 카테고리의 다른 글

백준 1932번: 정수 삼각형  (0) 2018.11.01
백준 2749번: 피보나치 수 3  (0) 2018.10.31
백준 2748번: 피보나치 수 2  (0) 2018.10.31
백준 2747번: 피보나치 수  (0) 2018.10.31
백준 2667번: 단지번호붙이기  (0) 2018.10.26

문제 출처: https://www.acmicpc.net/problem/2749




참고: https://png93.github.io/baekjoon-2749-fibonacci/

피보나치 수를 나눈 나머지는 항상 주기를 가진다. 이를 피사노 주기(Pisano Period)라 한다.

그림 출처: http://nackwon.tistory.com/52


피보나치 수를 나눌 수를 K라고 할 때,이면, 피사노 주기는 이다.

즉, k가 10의 6승인 1,000,000이면 피사노 주기는 1,500,000이다.

1,500,000번째 까지의 피보나치 수를 1,000,000로 나눈 나머지 값들을 구하면 그 이후의 수는 계산할 필요가 없다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(reader.readLine());
        int pisano = 1500000; // 피사노 주기
        long[] arr = new long[pisano];
        arr[0] = 0; arr[1] = 1;
 
        for(int i=2 ; i<pisano && i<=n ; i++){
            arr[i] = (arr[i-1] + arr[i-2]) % 1000000;  // 피보나치 수를 1,000,000 으로 나눈 나머지 값을 저장 
        }
 
        if(n >=pisano){
            n %= pisano;
        }
 
        System.out.println(arr[(int) n]);
    }
}
cs


저작자표시

'Algorithm' 카테고리의 다른 글

백준 1932번: 정수 삼각형  (0) 2018.11.01
백준 1149번: RGB거리  (0) 2018.11.01
백준 2748번: 피보나치 수 2  (0) 2018.10.31
백준 2747번: 피보나치 수  (0) 2018.10.31
백준 2667번: 단지번호붙이기  (0) 2018.10.26

문제 출처: https://www.acmicpc.net/problem/2748



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        long a = 0, b = 1, result = 0;
 
        if(n == 1){
            result = 1;
        }
        else {
            for(int i=2 ; i<=n ; i++){
                result = a + b;
                a = b;
                b = result;
            }
        }
 
        System.out.println(result);
    }
}
cs


저작자표시

'Algorithm' 카테고리의 다른 글

백준 1149번: RGB거리  (0) 2018.11.01
백준 2749번: 피보나치 수 3  (0) 2018.10.31
백준 2747번: 피보나치 수  (0) 2018.10.31
백준 2667번: 단지번호붙이기  (0) 2018.10.26
백준 2606번: 바이러스  (0) 2018.10.26

+ Recent posts

티스토리툴바