작은 기록공간

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();


        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        System.out.println(sum(arr, m));
    }

    public static int sum(int[] arr, int m){
        int sum, result = 0;

        for(int i = 0; i < arr.length-2; i++){
            for(int j = i+1; j < arr.length; j++){
                for(int k = j+1; k < arr.length; k++){
                    sum = arr[i] + arr[j] + arr[k];
                    if (sum == m){
                        return sum;
                    }else if (sum <= m){
                        result = Math.max(result, sum);
                    }
                }
            }
        }
        return result;
    }
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int i = 2;

        while(n != 1){
            if (n % i == 0) {
                System.out.println(i);
                n /= i;
                i = 2;
            }else {
                i++;
            }
        }
    }
}

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

풀이

주어진 영역내의 소수의 합과 최소값을 구해야 하므로

에라토스테네스의 체를 활용하였다.

해당 공식은 소수인 2 부터 시작하여 2의 배수를 모두 지우고, 이 다음 소수인 3의 배수를 모두 지우고...

이를 활용하면 주어진 범위내의 모든 소수를 쉽게 찾을수 있다.

1. 정수 m과 n을 입력받고 boolean 타입의 배열을 n+1 크기로 생성한다.
2. 반복문을 2부터 시작하여 배열의 값이 false인  경우 해당 값의 배수를 모두 true로 바꾼다.
3. 이렇게 하면 모든 소수는 false로 배열에 저장된다.
4. 나머지 0과 1은 따로 false 처리 한다.
5. m ~ n 범위의 배열중에서 값이 false인 배열을 찾는다.
6. 만약 sum이 0이라면 (첫번째 값이라면) 최소값이므로 저장한다.
7. sum에 모든 소수를 더해준다.
8. 최종적으로 sum이 0이라면 소수가 없는것이므로 -1을 출력하고 그외에는 sum과 최소값을  출력한다.

아래는 이를 구현한 코드이다.

// 에라토스테네스의 체
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        int min = 0;
        int sum = 0;

        boolean[] arr = new boolean[n+1];

        for (int i = 2; i < n+1; i++) {
            if (!arr[i]) {
                for (int j = i+i; j < n+1; j+=i) {
                    arr[j] = true;
                }
            }
        }

        arr[0] = true;
        arr[1] = true;

        for (int i = m; i < n+1; i++) {
            if (!arr[i]) {
                if(sum == 0) min = i;
                sum += i;
            }
        }

        if (sum == 0){
            System.out.println(-1);
        } else{
            System.out.println(sum);
            System.out.println(min);
        }

    }
}

이번 문제를 풀면서 몇번씩 쓰고 지우고를 반복했다.

뭔가 잘못된것 같으면 모두 주석처리하거나 다 지워버리고 처음부터 다시 생각하는게 도움이 되는 것 같다.

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

풀이

주어진 수 N개 중 소수를 찾으면 되는 문제이기에 나는 이렇게 풀었다.

1. N을 입력받아 반복문으로 입력을 받는다.
2. 입력 받은 수 m 의 값이 1보다 같거나 작으면  continue 한다.
3. 약수가 있는지 검사하고 약수가 존재하면 sum+1을 한다.
4. 소수는 약수가 1이고, 아니면 1 이상의 값을 가진다.
5. 약수가 1인 값만 count한다.
6. 결과를 출력한다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m, count = 0;
        int sum;

        for (int i = 0; i < n; i++) {
            m = sc.nextInt();

            if(m <= 1) continue;

            sum = 0;
            for (int j = 1; j <= m/2; j++) {
                if(m%j == 0){
                    sum += j;
                }
            }
            if(sum == 1) count++;
        }
        System.out.println(count);
    }
}

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

문제

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

풀이

2025.02.06 - [코테/백준] - 2501: 약수 구하기

이전에 풀었던 약수 구하기 문제의 응용버전이다.

위 문제에서 풀었듯이 n의 약수를 먼저 구하고, 약수를 모두 더한 값이 n과 같다면 합을 출력한다.

1. while문으로 무한 반복하며, n을 입력받고 n이 -1이라면 멈춘다.
2. 완전수는 n 자기자신을 제외한 모든 약수의  합이므로 n/2 의 값 만큼 for문을 반복한다.
3. 만약 약수라면 result 문자열에 형식에 맞춰 약수를 추가하고, sum에 값을 더한다.
4. for문이 끝나고 result의 마지막에 불필요한 ' + ' 를 제거한다.
5. if문으로 n과 sum값이 같은지 확인하여 같다면 result를 출력한다.
6. 같지 않다면 n is NOT perfect. 를 반환한다.

아래와 같이 코드로 구현하였다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n ,sum;
        String result;

        while(true){
            n = sc.nextInt();
            sum = 0;
            result = " = ";

            if (n == -1) break;

            for (int i = 1; i <= n/2; i++) {
                if(n%i == 0){
                    result = result + i + " + ";
                    sum += i;
                }
            }
            result = result.substring(0, result.length()-3);

            if (sum == n) {
                System.out.println(n + result);
            } else{
                System.out.println(n + " is NOT perfect.");
            }
        }

    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int count = 0;

        for (int i = 1; i <= n; i++) {
            if(n%i == 0){
                count++;
                if(count == k) {
                    System.out.println(i);
                    break;
                }
            }
        }
        if(count < k){
            System.out.println(0);
        }
    }
}

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

두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.

1. 첫 번째 숫자가 두 번째 숫자의 약수이다.
2. 첫 번째 숫자가 두 번째 숫자의 배수이다.
3. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.

약수와 배수를 구하는 문제로써

1. A 가 B의 약수 -> B/A 의 나머지가 0이면 약수
2. A 가 B의 배수 -> A/B 의 나머지가 0이면 배수
3. 모두 아니라면  약수와 배수가 모두 아니다

라고 생각했고 이를 코드로 구현하면 다음과 같다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(true){
            int a = sc.nextInt();
            int b = sc.nextInt();

            if (a == 0 && b == 0) break;

            if(b%a == 0){
                System.out.println("factor");
            }
            else if(a%b == 0){
                System.out.println("multiple");
            }
            else{
                System.out.println("neither");
            }
        }
    }
}

while문으로 무한 반복으로 입력을 받고, a와 b가 모두 0일때 입력을 멈추기로 했다.

그 외에 조건들은 모두 if문으로 나누어주었다.

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

이번 문제는 완전히 수학 문제였다.

먼저 문제에서는 달팽이가 막대를 타고 올라가는데 조건은 다음과 같다

- 막대의 높이는 V이다.
- 낮에 A 미터를 올라가고
- 밤에 B 미터를 미끄러진다
- 정상에서는 미끄러지지 않는다

최종적으로 달팽이가 막대를 올라가는데 며칠이 걸리는지 출력하면 된다.

반복문을 쓰면 간단하게 해결가능한 문제라고 생각하여 바로 작성해보았다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int v = sc.nextInt();
        int count = 1;
        int h = 0;

        while(true){
            h += a;
            if(h >= v){
                break;
            }
            h -= b;
            
            if(h >= v){
                break;
            }

            count++;
        }
        System.out.println(count);
    }
}

간단하게 while문으로 반복하면서 값을 비교하고 count를 출력하는 코드이다.

하지만 시간제한 0.25초 라는 제한이 있어서  이대로 제출하면 시간초과가 난다.

문제를 어떻게 풀까 많이 고민했는데 이 반례를 보고 규칙을 찾을 수 있었다.

input : 12 10 102
output : 51
answer : 46

먼저 달팽이가 하루에 올라갈 수 있는 높이를 계산하였다.

(올라간 거리) - (내려간 거리) = (하루동안 올라갈 수 있는 높이)
A - B = H

그 다음 달팽이가 마지막날에 도달하는 높이를 구한다.

(막대 높이) - (내려간 거리) = (도달 높이)
V - B = mH

왜 마지막날에 도달하는 높이를 따로 구하냐면,

달팽이는 막대의 끝에 도달하면 더이상 미끌어지지 않는다는 조건이 있기 때문에

최대 높이에서 미끌어진 거리까지가 달팽이의 마지막 날이 될 수 있기 때문이다.

이제 이렇게 구해진 값들을 나누면 달팽이가 막대를 등반하기 위해여 걸리는 총 날짜가 나온다.

(도달 높이) / (하루동안 올라갈 수 있는 높이)
mH / H = result

하지만 여기서 문제가 하나 생긴다.

만약에 나눈 숫자가 정수가 아니라 소수점 자리로 나온다면?

예를 들어

5 1 6

이렇게 값이 주어지는 경우 이러한 결과가 나온다.

A - B = 5 - 1 = 4
V - B = 6 - 1 = 5
5 / 4 = 1.25

손으로 그려봐도 달팽이가 정상까지 가는데 2일이 걸리므로

소수자리가 나온다면 올림해주면 된다.

그래서 처음에 해당 결과값을 float 형식으로 받아와서 소수점을 올림처리 하는 코드를 작성하였다.

하지만 3번째 예제에서 답이 다르게 나왔는데 아래와 같이 입력이 주어졌을 경우

100 99 1000000000

아래와 같이 출력되었다.

999999872 // 출력된 값
999999901 // 정답

이유를 알수없어서 검색을 해보았는데 부동 소수점 연산의 정확도 문제라고 한다.

이것을 해결하기 위해 if문을 사용하여 나머지가 0인 경우에는 그대로 출력하게 하고,

그 외에는 +1을 하도록 하게 코드를 수정하였다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(); // 올라간 거리
        int b = sc.nextInt(); // 내려간 거리
        int v = sc.nextInt(); // 막대

        if((v - b) % (a-b) == 0){
            System.out.println((v - b) / (a-b));
        } else{
            System.out.println(((v - b) / (a-b))+1);
        }
    }
}

이걸로 문제를 해결할 수 있었다.

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

아래 그림과 같은 무한한 배열이 주어진다.

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로

차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 할때  X번째 분수를 구하는 문제이다.

 

입력 범위가 X(1 ≤ X ≤ 10,000,000)로 꽤 넓고 시간제한은 0.5초로 짧다.

 

처음에 지그제그가 무슨 말이지 하고 직접 그림판으로 그려보니 이해가 되었다.

 

이 문제를 단순히 보이는 대로 배열로 풀었다간 무조건 시간 초과가 날 것이다.

그리고 지그제그로 되어있어 어떤 특정한 패턴을 찾아야 했다.

 

그래서 일단 지그제그 순서대로 표를 만들어서 써보았다.

순번	1	2	3	4	5
1	1/1
2	1/2	2/1
3	3/1	2/2	1/3
4	1/4	2/3	3/2	4/1
5	5/1	4/2	3/3	2/4	1/5

이렇게 하나하나 작성하고 보니 어떤 특정한 패턴이 보이기 시작했다.

 

1. 홀/짝수 번호에서 분모와 분자의 순서가 뒤바뀐다.

2. 최대 분모와 분자는 순번을 넘어가지 않는다. ex) 3번은 3을 넘지않음

3. 분모와 분자는 서로 1씩 늘어나거나 줄어든다.

 

이렇게 세가지 규칙을 찾아내었고 이걸 코드에 어떻게 적용할까 고민하였다.

일단 고려사항으로는

 

1. for문의 반복횟수를 최대한 줄여서 시간 복잡도를 줄여야 하고,

2. 홀/짝수 번호에서 분모와 분자의 위치를 서로 바꾸고 1씩 줄이거나 늘려야 한다.

 

그렇게 고민하다 생각해낸 방법은

해당 순번에서 최대/최소 값을 구해서 if문으로 분리하고, 연산해주는 방법을 떠올렸다.

그리고 홀/짝은 순번의 나머지 값을 비교하는 방식으로 분리하였다.

이제 코드로 구현해보면...

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        int sum = 0;

        while(true){
            if (n==1){
                System.out.println("1/1");
                break;
            }

            if(n <= sum){
                if (count%2==0){ // 짝수
                    System.out.printf("%d/%d",n-(sum-count),count-(n-(sum-count))+1);
                    break;
                }
                else{            // 홀수
                    System.out.printf("%d/%d",count-(n-(sum-count))+1,n-(sum-count));
                    break;
                }
            }
            count++;      // 카운트
            sum += count; // 최대값
        }
    }
}

while문으로 무한 반복을 돌리고

1의 경우에는 예외처리를 해주었고

count와 sum을 만들어서 각 순번과 최대값을 구할 수 있게 했다.

중간에 수식이 꽤 난잡한데 풀어서 정리하자면

(sum-count)

- 최대값과 카운트를 빼서 해당 순번의 최소값을 구했다.

n-(sum-count)

- n과 최소값을 빼서 분모/자를 만들었다.

count-(n-(sum-count))+1

- 분/모자 값에 순번을 빼서 역의 값이 나오도록 했다. 1로 값을 세부 조정했다.

이렇게 쓰고나니깐 뭔가 더 많이 복잡한데 일단 문제를 해결하긴 했다.

메모리는 17748 kb , 시간은 176ms가 걸렸다.

역시 문제를 풀때는 종이에 한번 써보는게 생각을 정리하는데 많은 도움이 되는것 같다.