백준 11659, 11660, 2018(Java)

📚 Do it 알고리즘 코딩테스트 교재를 참고하며 백준 문제를 푸는중이다. 

📚 잠깐의 사담 하자면, 파이썬도 잠깐 해보고 C++로도 했었는데, Spring 쪽으로 가고 싶어진 이후로는 Java공부를 다시 해야겠다고 생각해서 자바로 돌아가게 되었다. 뭔가 마음의 고향 온 것 같으면서도... 암튼 그렇다. 이제 언어 바꾸지말고 열심히 해야지... 

 

11659

- input값이 여러개 나오니까 Scanner보다 BufferedReader 사용해서 입력 받기. 

- 문제에서 인덱스1부터 세는게 편하면 개인적으로는.. 그냥 쿨하게 배열을 한칸 더 만들어 두는 것이 안 헷갈리고 괜찮은 것 같다. 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine()); // 첫 줄 원소 개수, 질의 개수 입력받음
        int num = Integer.parseInt(stringTokenizer.nextToken());
        int query = Integer.parseInt(stringTokenizer.nextToken());

        // 굳이 각 원소들을 저장할 필요는 없다. 구간합만 출력해달라 했기 때문

        long[] sumArray = new long[num + 1]; // 헷갈리지 않게 원소 개수 자체를 1개 더 여유있게. 
        stringTokenizer = new StringTokenizer(br.readLine()); // 원소 나열해주는 줄 읽음. 
        
        // 배열에 넣는 작업
        for (int i = 1; i <= num; i++) {
            sumArray[i] = Long.parseLong(stringTokenizer.nextToken()) + sumArray[i-1];
        }

        // 출력 작업
        for (int q = 0; q < query; q++) {
            stringTokenizer = new StringTokenizer(br.readLine()); // 각 줄 별 질의 읽어줌.
            int start = Integer.parseInt(stringTokenizer.nextToken());
            int end = Integer.parseInt(stringTokenizer.nextToken());

            System.out.println(sumArray[end] - sumArray[start-1]);
        }
    }
}

 

11660

- 위에가 단순 1차원 배열이었다면, 이건 2차원 배열이다. 실버1정도의 난이도라는데, 코테 초보인 내겐 좀 시간이 걸렸다... 

- 11659, 11660 두 문제 다 구간 합 배열로 계산하는 문제인데 2차원은 좀 더 이해하기 어려우니(?) 그림도 그렸다.

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(stringTokenizer.nextToken());
        int query = Integer.parseInt(stringTokenizer.nextToken());
        
        int original[][] = new int[size+1][size+1];
        int sum[][] = new int[size+1][size+1];

        for (int i = 1; i <= size; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 1; j <= size; j++) {
                original[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                sum[i][j] = sum[i-1][j] + sum[i][j-1] + original[i][j] - sum[i-1][j-1];
            }
        }

        for (int q = 0; q < query; q++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            int rowStart = Integer.parseInt(stringTokenizer.nextToken());
            int colStart = Integer.parseInt(stringTokenizer.nextToken());
            int rowEnd = Integer.parseInt(stringTokenizer.nextToken());
            int colEnd = Integer.parseInt(stringTokenizer.nextToken());

            System.out.println(sum[rowEnd][colEnd] - sum[rowEnd][colStart-1] - sum[rowStart-1][colEnd] + sum[rowStart-1][colStart-1]);
        }
    }
}

 

2018

- 예전에 C++로 풀었었던 문제이다. 아래 링크에 코드에 대한 설명을 자세히 써놨다. 

- 교재에서는 투 포인터 알고리즘으로 풀 수 있게끔 되어있는데, 두 코드 모두 돌려보니 메모리사용량은 같고 시간은 내 코드가 조금 더 빨라서 일단 기억은 내 코드로 해두려 한다 ㅎㅎ...

- 덧셈을 구성하는 자연수개수로 규칙을 찾아낸 다음에 짰더니 간단해졌다. 

 

https://bubblebubble.tistory.com/22

연속된 자연수의 합 (백준 2018번 : 수들의 합 5)

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int temp = num;
        int count = 1;
        int pivot = 1;
        for (int i = 2; pivot < temp; i++) {
            if ((temp - pivot) % i == 0) {
                count++;
            }
            pivot += i;
        }
        System.out.println(count);
        sc.close();
    }
}