Minimum Operation

문제

 

 

 

풀이

- 주어진 코드

 

import java.util.*;

class MinimumOperations {
    private static final Scanner scan = new Scanner(System.in);
    int n, r ,g, b;
    int[][] dp = new int[110][1<<3];

    Vector<Integer> red = new Vector();
    Vector<Integer> green = new Vector();
    Vector<Integer> blue = new Vector();

    public void get() {
         n = scan.nextInt();

        for (int i = 0; i < n; i++) {
            r = scan.nextInt();
            g = scan.nextInt();
            b = scan.nextInt();
            red.add(r);
            green.add(g);
            blue.add(b);
        }
    }

    public void minOperations() {
        int i, j;
        for (i = 0; i < n; i++) {
            for (j = 0; j < 7; j++) {
                dp[i][j] = (1<<30);
            }
        }
        dp[0][0] = 0;
        for (i = 0; i < n; i++){
            for (j = 0; j < 7; j++){
                dp[i + 1][j | 1] = Math.min(dp[i + 1][j | 1], dp[i][j] + green.get(i) + blue.get(i));
                dp[i + 1][j | 2] = Math.min(dp[i + 1][j | 2], dp[i][j] + red.get(i) + blue.get(i));
                dp[i + 1][j | 4] = Math.min(dp[i + 1][j | 4], dp[i][j] + blue.get(i) + green.get(i));
            }
        }
        j = 0;
        for (i = 0; i < n; i++){
            if (green.get(i) != 0) j |= 1;
            if (red.get(i) != 0) j |= 2;
            if (blue.get(i) != 0) j |= 4;
        }
        if (dp[n][j] >= (1<<30)) dp[n][j] = -1;
            System.out.println(dp[n][j]);
    }
}
class Solution {
    public static void main(String[] args) {
        MinimumOperations obj = new MinimumOperations();
        obj.get();
        obj.minOperations();
    }
}

 

" Each bit in j should track whether or not a box containing only balls of a certain color is already provided in the partial solution. "

 

- 공부

 

* 비트 쉬프트 연산자 

1 << 30     =    2의 31승

1이라는 녀석의 비트값을 30만큼 왼쪽으로 이동시키겠다.

 

1 << 1      =   10(2)  =   4  =  2의 2승

1 << 2      =   100(2)  =   8  =  2의 3승

...

1 << 30    =   1000000 ...  =  1073741824  =  2의 31승

 

 

* 비트 단위 논리 연산자  

| : or 연산 

ex) C = A | B 

      A와 B를 비트단위 OR 연산 후 C에 대입

ex) A |= B

     좌변과 우변의 값을 비트단위 OR 연산 후에 좌변에 대입,  A = A | B 와 동일 

 

 

 

 

참고

- 비트 시프트 연산자
https://secretroute.tistory.com/entry/자바의神-Vol1-비트-시프트-연산자 [EMPTY]

자바의神 Vol.1 : 비트 시프트 연산자

- 비트 단위 논리 연산자

https://jhrun.tistory.com/133 [JHRunning]

[Android/JAVA] 자바 연산자(그리고, 또는, etc)를 사용하여 효과적으로 개발하기