[JAVA] 백준 구현 뿌수기1

 

 

대망의 구현 뿌수기다. 가장 기본이면서 가장 중요하고 문제도 가장 많다. 

긴 여정이 될 것 같다.

 

 

2167 2차원 배열의 합 - 실버5

https://www.acmicpc.net/problem/2167

2167번: 2차원 배열의 합

• 누적합 냄새가 너무 나서 그렇게 풀었다

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N+1][M+1];

        for (int i =1; i<N+1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j =1; j<M+1; j++)
                arr[i][j] = Integer.parseInt(st.nextToken()) + arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
        }

        int cnt = Integer.parseInt(br.readLine());

        for (int c=0; c<cnt; c++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            System.out.println(arr[x][y] - arr[x][j-1] - arr[i-1][y] + arr[i-1][j-1]);
        }
    }
}

• 역시나 맞았다

 

 

 

 

2563 색종이 - 실버5

https://www.acmicpc.net/problem/2563

2563번: 색종이

• 진짜 너무 안풀려서 힘들었다
• 결국 풀이를 찾아봤는데 허무했음..

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());

        StringTokenizer st;

        int[][] arr = new int[100][100];

        for (int i =0; i<cnt; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            for (int j=0; j<10; j++) {
                if (x+j == 100)
                    break;

                for (int k=0; k<10; k++) {
                    if (y+k == 100)
                        break;

                    arr[x+j][y+k] = 1;
                }
            }
        }

        int result = 0;
        for (int i =0; i<100; i++) {
            for (int j =0; j<100; j++) {
                if (arr[i][j] == 1)
                    result += 1;
            }
        }

        System.out.println(result);
    }
}

• 짜증나서 설명은 생략한다

 

 

 

 

1158 요세푸스 문제 - 실버4

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

• 좋은 방법이 떠오르지 않아 큐에다 무작정 넣고 뺐다
• 시간초과가 나길 바랐지만 시간초과는 나지 않았다

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        Queue<Integer> queue = new LinkedList<>();
        for (int i= 1; i<=n; i++) {
            queue.add(i);
        }

        int[] arr = new int[n];
        int idx = 0;

        while (idx != n) {
            for (int i =0; i<k-1; i++) {
                queue.add(queue.poll());
            }

            arr[idx] = queue.poll();
            idx++;
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");
        for (int i =0; i<arr.length; i++) {
            sb.append(arr[i]);
            if (i != arr.length-1) {
                sb.append(", ");
            }
        }

        sb.append(">");
        System.out.println(sb);
    }
}

 

 

 

 

1244 스위치 켜고 끄기 - 실버4

https://www.acmicpc.net/problem/1244

1244번: 스위치 켜고 끄기

• 여자의 경우 현재 바뀐 값이 꼭 필요하기 때문에 하라는 대로 다 바꿔줬다

 

public class Main {
    static boolean[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());
        arr = new boolean[cnt+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i =1; i<arr.length; i++) {
            int value = Integer.parseInt(st.nextToken());
            if (value == 1) 
                arr[i] = true;
        }

        int studentCnt = Integer.parseInt(br.readLine());
        for (int i =0; i<studentCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int gender = Integer.parseInt(st.nextToken()); //1이면 남자, 2면 여자
            int number = Integer.parseInt(st.nextToken());

            if (gender == 1) 
                manChange(number);
            else 
                womanChange(number);
        }

        StringBuilder sb= new StringBuilder();
        for (int i=1; i<arr.length; i++) {
            if (arr[i] == true)
                sb.append("1");
            else
                sb.append("0");

            if (i % 20 == 0) 
                sb.append("\n");
            else 
                sb.append(" ");
        }

        System.out.println(sb);
    }

    private static void womanChange(int number) {
        arr[number] = !arr[number];
        for (int a = 1; a<arr.length; a++) {
            if (number - a >= 1 && number + a < arr.length && arr[number -a] == arr[number +a]) {
                arr[number -a] = !arr[number -a];
                arr[number +a] = !arr[number +a];
            } else {
                break;
            }
        }
    }

    private static void manChange(int number) {
        int n= number;
        while (n < arr.length) {
            arr[n] = !arr[n];
            n += number;
        }
    }
}

• 출력형식에서 20마다 라인을 바꿔야한다는 것만 조심하면 될 것 같다(정답률 20퍼의 원인인듯)

 

 

 

 

1748 수 이어 쓰기 1 - 실버4

https://www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

• 분명 그냥 세면 시간초과가 날 것 같아서 규칙을 찾았다
  • 1~9까지            : 1자릿수이고 9개
  • 10~99까지        : 2자릿수이고 90개
  • 100~999까지    : 3자릿수이고 900개
  • 1000~9999까지: 4자릿수이고 9000개
• 이 식으로 풀어내면 어렵지 않게 풀어낼 수 있음

 

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int n = Integer.parseInt(input);
        int size = input.length();

        long result = 0L;
        long cntNumber = 9;
        int start = 1;
        int currentSize = 1;
        while (currentSize < size) {
            result += cntNumber * currentSize;
            cntNumber *= 10;
            start *= 10;
            currentSize++;
        }

        result += (n - start + 1) * currentSize;

        System.out.println(result);
    }
}