백준(1010, 1966,2839)

문제 1010번(정답, 소요시간10분)

소스코드

import java.io.*;
import java.util.StringTokenizer;
public class boj1010 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb=  new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            long result = 1;
            for (int j = 0; j < n; j++) {
                result *= (m-j);
                result /= (j+1);
            }
            sb.append(result + "\n");
        }
        System.out.println(sb);
    }
}

풀이 접근

1. 해당 문제가 조합 경우의 수를 구하는 문제임을 확인한다.
2. M의 범위가 30까지 가능하므로 결과를 저장하는 변수는 long으로 생성한다.
3. 만약의 상황에 대비해 하나의 반복문에 밑변까지 같이 계산한다.

   for (int j = 0; j < n; j++) {
                  result *= (m-j);
                  result /= (j+1);
              }

문제 핵심

• 시간복잡도를 고려하여 코드 작성!
• 기초수학 - 조합에 대한 이해

문제 1966 (정답, 소요시간2시간)

소스코드

import java.io.*;
import java.util.*;
public class boj1966 {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            Queue<int[]> qu = new LinkedList<>();
            int cnt = 0;
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                qu.offer(new int[] {j, Integer.parseInt(st.nextToken())});
            }
            while(!qu.isEmpty()) {
                int max = -1;
                for (int j = 0; j < qu.size(); j++) {
                    if (qu.peek()[1] > max) {
                        max = qu.peek()[1];
                    }
                    qu.offer(qu.poll());
                }
                if (qu.peek()[0] == m && qu.peek()[1] == max) {
                    cnt++;
                    qu.poll();
                    break;
                }
                if (qu.peek()[1] == max) {
                    cnt++;
                    qu.poll();
                } else {
                    qu.offer(qu.poll());
                }
            }
            sb.append(cnt + "\n");
        }
        System.out.println(sb);
    }
}

풀이 접근

1. Queue의 선입선출구조를 생각한다.
2. Queue를 2차원 배열로 만들어서 0번째 배열에는 index 값을 1번째 배열에는 우선순위 값을 넣는다.
3. 반복문을 통해서 우선순위가 높은 값을 max 변수에 저장한다.
4. queue에 peek값의 index가 M과 같고 peek값의 우선순위가 max와 같으면 반복문을 종료한다
5. 만약 peek값의 우선순위만 max값과 같다면 해당 queue를 삭제하고 반복문을 다시 돌린다. 둘 다 아닌 경우에는 peek값을 맨 앞으로 옮겨준다.
6. 반복문이 끝나면 카운트 했던 숫자를 출력한다.

이해를 돕기 위한 연습장...?

문제 핵심

• Queue 자료구조에 대해 이해하고 있는지!
• 우선순위와 인덱스 값을 묶어서 혹은 같이 바꿀 수 있는지!

문제 2839번(정답, 소요시간30분)

소스코드

import java.io.*;
public class boj2839 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt=0;
        int n = Integer.parseInt(br.readLine());
        while(true){
            if(n%5 == 0){
                cnt+=n/5;
                System.out.println(cnt);
                return;
            }else{
                n -=3;
                cnt++;
            }
            if(n<0){
                System.out.println(-1);
                return;
            }
        }
    }
}

풀이 접근

1. 입력 받은 n의 값을 5a+3b라고 생각해 본다.
2. a가 최대일 경우를 출력하는 문제다.
3. 반복문을 통해 n의 값을 계속해서 3씩 빼주고, 5로 나누어 떨어지는 값이 나왔을 때, n을 5로 나눈 값을 추가하고 반복문을 종료한다.
4. 만일 5a+3b로 딱 떨어지지 않고, n의 값이 음수까지 떨어지면 -1을 출력하고 반복문을 종료한다.