#유형 : 그리디, 규칙

#난이도 : 실버 1

# 입력받는 숫자 N이 2^n일 경우, 물병을 하나로 합칠수 있음(2, 4, 8, 16 .. )

# 물병을 하나로 합쳐가며 K개를 넘기지 않도록 반복문을 돌린다.

 

1. 입력받는 숫자 N을 물병 하나로 합쳐간다.(N/=2)

2. 1번의 과정에서 나머지가 발생하는 경우 COUNT += 1

3. 반복문을 돌리며, COUNT가 K보다 작은 경우 리턴

4. 아닌 경우, N에 숫자를 더해가며 반복

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
30
31
32
33
34
35
36
37
38
39
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1052 {
    static int N,K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        int pls = 0;
        while(true) {
            
            int tmp = N + pls;
            int count = 0;
            
            while(tmp > 0) {
                
                if(tmp % 2 != 0)
                    count++;
                //System.out.println(tmp + " // " + count);
                tmp /= 2;
                
            }
            
            if(count <= K)
                break;
            
            pls++;
        }
        
        System.out.println(pls);
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1038 괄호 - Java 자바  (0) 2021.11.21
#백준_9012 괄호 - Java 자바  (0) 2020.07.06
#백준_10828 스택 - Java 자바  (0) 2020.07.06
#백준_1629 곱셈 - Java 자바  (0) 2020.07.01
#백준_2096 내려가기 - Java 자바  (0) 2020.06.27

#유형 : 브루트포스, 큐

#난이도 : 골드5

# 큐를 사용하면 생각보다 편하게 접근할 수 있던 문제

# 큐에 1~9를 미리 넣어놓고 헤드부터 poll하면서 num % 10 한 만큼 반복문을 돌려 더하면 된다.

아래의 로직을 잘 생각하면 해결할 수 있다.

# 주의해야할 점은 int 형으로 하면 범위문제로 long으로 접근

for(int i=0; i<num%10; i++)

{

     Arr[idx] = num * 10 + i;

}

Ex) 1 -> 1*10 + 0 = 10

Ex) 2 -> 2*10 + 0 = 20

Ex) 2 -> 2*10 + 1 = 21 

. . . 

 

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1038 {    
    static int idx = 9;
    static int N;
    static Queue<Long> queue = new LinkedList<Long>();
    static long arr[] = new long[1000001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for(int i=1; i<10; i++) {
            queue.add((long) i);
            arr[i] = i;
        }
        
        solve();
        if(N!=0 && arr[N] == 0) {
            System.out.println("-1");
        }else {
            System.out.println(arr[N]);
        }
    }
    
    public static void solve() {
        while(idx <= N) {
            if(queue.isEmpty()) {
                return;
            }
            
            long num = queue.poll();
            long lastNum = num % 10;
            
            for(int i=0; i<lastNum; i++) {
                queue.add((num * 10) + i);
                arr[++idx] =(num * 10) + i;
            }
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1052 물병 - Java 자바  (0) 2021.12.06
#백준_9012 괄호 - Java 자바  (0) 2020.07.06
#백준_10828 스택 - Java 자바  (0) 2020.07.06
#백준_1629 곱셈 - Java 자바  (0) 2020.07.01
#백준_2096 내려가기 - Java 자바  (0) 2020.06.27

#유형 : 스택

#난이도 : 실버4

# ( 와 )  들어올 때 케이스를 나누어서 구현하면 된다. ( 는 앞에 무엇이 있던 스택에 넣을 수 있고, )는 앞에 ( 가 없거나 스택이 비어있다면 넣을 수 없다.

 

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class p9012 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            solve(str);
        }
        
    }
 
    private static void solve(String str) {
        // TODO Auto-generated method stub
        Stack<Character> stack = new Stack<>();
        
        for(int i=0; i<str.length(); i++) {
            char ch = str.charAt(i);
            if(ch == '(') {
                stack.push(ch);
            }else {
                if(stack.size() == 0) {
                    System.out.println("NO");
                    return;
                }
                
                if(stack.peek() != '(') {
                    System.out.println("NO");
                    return;
                }else
                    stack.pop();
            }
        }
        
        if(stack.size() == 0)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
    
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1052 물병 - Java 자바  (0) 2021.12.06
#백준_1038 괄호 - Java 자바  (0) 2021.11.21
#백준_10828 스택 - Java 자바  (0) 2020.07.06
#백준_1629 곱셈 - Java 자바  (0) 2020.07.01
#백준_2096 내려가기 - Java 자바  (0) 2020.06.27

#유형 : 스택

#난이도 : 실버 4

# 스택의 기본 문제, 명령 종류와 조건에 따라 구현하면 된다.

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
30
31
32
33
34
35
36
37
38
39
40
41
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class p10828 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            if(cmd.equals("push")) {
                int val = Integer.parseInt(st.nextToken());
                stack.push(val);
            }else if(cmd.equals("pop")) {
                if(stack.isEmpty())
                    System.out.println(-1);
                else
                    System.out.println(stack.pop());
            }else if(cmd.equals("size")) {
                System.out.println(stack.size());
            }else if(cmd.equals("empty")) {
                if(stack.isEmpty())
                    System.out.println(1);
                else
                    System.out.println(0);
            }else {
                if(stack.isEmpty())
                    System.out.println(-1);
                else
                    System.out.println(stack.peek());
            }
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1038 괄호 - Java 자바  (0) 2021.11.21
#백준_9012 괄호 - Java 자바  (0) 2020.07.06
#백준_1629 곱셈 - Java 자바  (0) 2020.07.01
#백준_2096 내려가기 - Java 자바  (0) 2020.06.27
#백준_2473 세 용액 - Java 자바  (0) 2020.05.11

#유형 : 수학, 분할 정복, 재귀

#난이도 : 실버 1

# A,B,C의 값이  2,147,483,647 이하이기 때문에, 단순하게 for문을 돌리면 시간복잡도가 너무 답이 없다. 

여기서 분할 정복의 바탕인 재귀를 사용한다면 어떻게 될까?

2^31이 약 2,147,483,647 이기 때문에, 2,147,483,647 번 돌리는 반복문 댓긴 재귀 방식을 활용하면 31번의 연산으로 퉁칠수 있다. 

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
30
31
32
33
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1629 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        long A,B,C;
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());
        C = Long.parseLong(st.nextToken());
        
        System.out.println(solve(A%C, B, C));
    }
    
    public static long solve(long a, long b, long c) {
        if(b == 1)
            return a;
        else {
            long next = solve(a, b/2, c);
            if(b%2 == 1) {
                return ((next * next) % c * a) % c;
            }else
                return (next*next)%c;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_9012 괄호 - Java 자바  (0) 2020.07.06
#백준_10828 스택 - Java 자바  (0) 2020.07.06
#백준_2096 내려가기 - Java 자바  (0) 2020.06.27
#백준_2473 세 용액 - Java 자바  (0) 2020.05.11
#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06

#유형 : 다이나믹 프로그래밍

#난이도 : 골드 4

# 다이나믹 프로그래밍의 전형적인 문제로, 현 위치에서 어디로 내려갈 수 있는가를 따지면 된다. 인덱스를 1,2,3 이라고 하였을 때

 

1) 인덱스 1에서는 아래층의 1,2 로 이동할 수 있다 => dp[i][1] = Math.max or min(dp[i-1][1], dp[i-1][2]) + arr[i][1])

2) 인덱스 2에서는 아래층의 1,2,3으로 이동할 수 있다 => dp[i][2] = Math.max or min(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + arr[i][2])

3) 인덱스 3에서는 아래층의 2,3 으로 이동할 수 있다 => dp[i][3] = Math.max or min(dp[i-1][2], dp[i-1][3]) + arr[i][3])

 

이 점화식으로 알고리즘을 짜면 된다. 맨 처음에 생각없이 배열을 [N][N] 사이즈로 했다가 메모리초과가 계속 발생해서 왜 그런지 한참 수정했다.. 2) 를 굳이 줄이자면 min이던, max던 dp[i][1]에서 max 또는 min값을 미리 계산했기 때문에 Math.max or min(dp[i][1] - arr[i][1], dp[i-1][3]) + arr[i][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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package bj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p2096 {
    static int N;
    static int arr[][];
    static int max[][], min[][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][4];
        max = new int[N+1][4];
        min = new int[N+1][4];
        
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i=1; i<=N; i++) {
            max[i][1] += Math.max(max[i-1][1], max[i-1][2]) + arr[i][1];
            max[i][2] += Math.max(Math.max(max[i-1][1], max[i-1][2]), max[i-1][3]) + arr[i][2];
            max[i][3] += Math.max(max[i-1][2], max[i-1][3]) + arr[i][3];
            
            min[i][1] += Math.min(min[i-1][1], min[i-1][2]) + arr[i][1];
            min[i][2] += Math.min(Math.min(min[i-1][1], min[i-1][2]), min[i-1][3]) + arr[i][2];
            min[i][3] += Math.min(min[i-1][2], min[i-1][3]) + arr[i][3];
        }
        
        int maxValue = 0, minValue = Integer.MAX_VALUE;
        for(int i=1; i<=3; i++) {
            maxValue = Math.max(maxValue, max[N][i]);
            minValue = Math.min(minValue, min[N][i]);
        }
        
        System.out.println(maxValue+" " +minValue);
    }
}
 cs

'백준' 카테고리의 다른 글

#백준_10828 스택 - Java 자바  (0) 2020.07.06
#백준_1629 곱셈 - Java 자바  (0) 2020.07.01
#백준_2473 세 용액 - Java 자바  (0) 2020.05.11
#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06
#백준_2056 작업 - Java 자바  (0) 2020.05.05

#유형 : 투 포인터, 탐색, 정렬

#난이도 : 골드 4

# 인덱스를 이동하면서 투포인터 개념을 사용하면 해결할 수 있던 문제.

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class p2473 {
    static int N, idx1, idx2, idx3;
    static int arr[];
    static long minValue = Long.MAX_VALUE;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr= new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        
        solve();
        
        System.out.println(arr[idx1]+" "+arr[idx2]+" "+arr[idx3]);
    }
    private static void solve() {
        // TODO Auto-generated method stub
        for(int i=0; i<N; i++) {
            int j = i+1;
            int k = N-1;
            while(j<k) {
//                System.out.println(arr[i]+" "+arr[j]+" "+arr[k]);
                long sum = arr[i] + arr[j] + arr[k];
                if(Math.abs(sum) < minValue) {
                    idx1 = i;
                    idx2 = j;
                    idx3 = k;
                    minValue = Math.abs(sum);
                }
                //양수를 더해야하므로 j++
                if(sum < 0) {
                    j++;

                }else {
                    k--;
                }
            }
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1629 곱셈 - Java 자바  (0) 2020.07.01
#백준_2096 내려가기 - Java 자바  (0) 2020.06.27
#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06
#백준_2056 작업 - Java 자바  (0) 2020.05.05
#백준_2407 조합 - Java 자바  (0) 2020.05.04

#유형 : 다이나믹 프로그래밍

#난이도 : 실버 1

#조건은 다음과 같다

  • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

요약하면 인접한 집은 색이 같으면 안된다는 것이다. 아래와 같은 사항을 dp로 풀어내면 된다.

1. 전에 빨강을 칠했다 => 파랑,초록

2. 전에 파랑을 칠했다 => 빨강,초록

3. 전에 초록을 칠했다 => 빨강,파랑 

 

 

dp[i][1]이 빨강색이라고 가정하면, 그 전에는 파랑,초록을 칠해야 한다. 따라서 dp[i-1][2](파랑), dp[i-1][3](초록) 둘 중 한개에서 빨강의 값을 더해주는 것이다.

 

즉 아래와 같이 dp를 풀어내면 된다.

dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + arr[i][1];

dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + arr[i][2];

dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][3];

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1149 {
    static int N;
    static int arr[][];
    static int dp[][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        dp = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 0 : 빨강, 1 : 파랑, 2 : 초록
        int result = solve();
        
        System.out.println(result);
    }
    private static int solve() {
        // TODO Auto-generated method stub
        // 0 : 빨강, 1 : 파랑, 2 : 초록 
        dp[1][1] = arr[1][1];
        dp[1][2] = arr[1][2];
        dp[1][3] = arr[1][3];
        
        //1번 집의 색은 2번 집의 색과 같지 않아야 한다.
        //N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
        //i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
        // 요약하면 인접한 집은 색이 같으면 안된다는 것 => 1. 전에 빨강을 칠했다 => 파랑,초록 // 2. 전에 파랑을 칠했다 => 빨강,초록 // 3. 전에 초록을 칠했다 => 빨강,파랑 
        for(int i=2; i<=N; i++) {
            dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + arr[i][1];
            dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + arr[i][2];
            dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][3];
        }
        int rs = Integer.MAX_VALUE;
        
        for(int i=1; i<=3; i++)
            rs = Math.min(rs, dp[N][i]);
        
        return rs;
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2096 내려가기 - Java 자바  (0) 2020.06.27
#백준_2473 세 용액 - Java 자바  (0) 2020.05.11
#백준_2056 작업 - Java 자바  (0) 2020.05.05
#백준_2407 조합 - Java 자바  (0) 2020.05.04
#백준_2467 용액 - Java 자바  (0) 2020.05.03

+ Recent posts

티스토리툴바