작은 기록공간

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가 걸렸다.

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

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

이 문제는 아래 그림에 주어지는 것과 같이

100*100 사이즈의 도화지에 검은색 색종이를 붙이는데, 이 색종이가 붙은 부분의 넓이를 구하는 문제이다.

이, 때 색종이의  크기는 10*10으로 고정이고 도화지 바깥으로 나가는 경우는 없다.

해당 이미지에서 주어진 입력은 아래와 같고,

3
3 7
15 7
5 2

출력되는 결과는

260

이 나오게 된다.

이 문제는 정말 하루종일 고민을 했었는데 결론적으론 내가 문제를 제대로 안 읽어서 일어난 일이었다.

문제를 풀기 위해 여러 가지 고민을 했는데,

1. 어차피 색종이의 총넓이는 N*100이다 여기서 겹치는 부분을 계산해서 빼면 된다.

2. 이중배열을 이용하는 문제니 깐 배열에 주어진 가로세로 길이를 넣고 하나씩 꺼내서 비교하자

3. 그다음 겹치는 부분을 계산해서 그 넓이를 구하고 총넓이의 값에 빼주자

이렇게 생각하고 길고 복잡한 코드를 짰다.

import java.util.Scanner;

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

        int w = 0;
        int h = 0;

        int[][] arr = new int[n][2];

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

        int count = 0;
        for (int i = 0; i < n-1; i++) {
            for (int j = count; j < n-1; j++) {
                w = Math.abs(arr[i][0] - arr[j+1][0]);
                h = Math.abs(arr[i][1] - arr[j+1][1]);
                if (w < 10 && h < 10) {
                    result -= ((w*2)*(h*2));
                }
            }
            count++;
        }
        System.out.println(result);

    }
}

당연하게도 바로 틀렸다.

딱 첫 번째 주어진  예제만 통과할 수 있는  코드였기 때문에 당연한 결과였다.

이 문제를 가지고 머리를 싸매고 고민하다가 친구가 왜 이걸 못 푸냐고 힌트를 줬는데

어차피 도화지의 크기는 정해져 있으니깐 배열로 도화지를 그리고 색종이의 위치에 맞게 1을 넣으면 되지 않냐고 했다.

도화지의  크기가 정해져 있다고?

전혀 생각하지 못했다.

도화지의 크기가 정해져 있다는 게 문제에 써져 있는데 그것도 제대로 안 읽고 삽질하고 있었다.

그래서 바로 코드를 모두 지우고 새롭게 다시 작성했다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;
        int[][] arr = new int[100][100]; // 가로 세로 크기가 각각 100인 도화지

        int h,w;

        for (int i = 0; i < n; i++) {
            h = sc.nextInt();
            w = sc.nextInt();
            for (int j = h; j < h+10; j++) {
                for (int k = w; k < w + 10; k++) {
                    arr[j][k]++;
                }
            }
        }

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

        System.out.println(result);
    }
}

먼저 처음 배열에 도화지의 크기를 집어넣고,

가로세로를 입력받을 때마다 해당 위치에  1 씩 값을 더해줬다.

모든 작업이 끝나고 이제 값이 1 이상인 부분의 합을 구하고 출력한다.

아니면 어차피 면적만 구하는 거니깐 boolean 값을 써줘도 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;
        boolean[][] arr = new boolean[100][100]; // 가로 세로 크기가 각각 100인 도화지

        int h,w;

        for (int i = 0; i < n; i++) {
            h = sc.nextInt();
            w = sc.nextInt();
            for (int j = h; j < h+10; j++) {
                for (int k = w; k < w + 10; k++) {
                    arr[j][k] = true;
                }
            }
        }

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

        System.out.println(result);
    }
}

boolean로 수정하면 더 적은 메모리를 먹을 줄 알았는데

생각보다 그렇게 유의미한 결과는 안 나왔다.

아무튼 다음부턴 문제를 제대로 읽어야겠다.

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

이번 문제는 4개의 점을 가진 정사각형을 둘러싸는 문제이다.

먼저 4개의 점을 가진 정사각형의 주변에 3개의 정사각형을 더 둘러싸되 동일한 면은 겹치게 하여 점의 개수를 줄였다.

처음 이 그림을 봤을때는 설마 검은  점의 개수를 세라는건 아니겠지 했는데

당연히 그런건 아니고 검은 점은 겹치는 부분을 시각적으로 표시해둔 것이였다.

이것도 배열로 풀어야 하나 그럼 어떻게 계산해야하지 고민하면서 노트에 끄적이다가 공식을 찾아냈다.

2 + 1 = 3
-> 3 * 3 = 9

3 + 2 = 5
-> 5 * 5 = 25

i + (i-1) = n
-> n * n = reuslt

이런 공식이 성립되었다.

그래서 이것을 코드로 다시 풀어내면

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 3;               // 초기값

        for(int i = 1; i < n; i++) {
            result += (result - 1);
        }

        System.out.println(result * result);
    }
}

여기서 초기값을 3으로 준 이유는 첫 상태가 하나의 정사각형인 4가 아니고

이미 한번 계산한 후의 정사각형이기에 그 연산은 바로 건너뛰도록 했다.

이 문제에서 N의 범위가  (1 ≤ N ≤ 15) 이기 때문에

사실 정답만 안다면 그냥 if문이나 switch문으로 하드코딩 해버려도 정답이 아닐까 생각이 든다.물론 그렇게 하면 이 문제의 의미가 없어지기도 하고 정답을 알정도면 해법도 알고있겠지만 말이다.

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

이번 문제는 아래의 그림 처럼 육각형으로 이루어진 벌집에서

중앙의 1 부터 시작해서 이웃하는 방에 돌아가며 1씩 증가하는 숫자로 번호를 매기는데,

숫자 N이 주어졌을 때 중앙 1에서 부터 N까지 지나가는 최소한의 방의 숫자를 구하는 문제이다.

예를 들어 N = 13 이라면 3개, N = 58 이라면 5개를 지나간다.

처음에 이 문제를 보았을때 든 생각은

방을 어떻게 처리해야할까 배열을 만들어서 하나씩 생성하고 넘겨짚어야 하나?

아니면 '육각형'이라고 했으니깐 각 블럭마다 6개의 경우의 수가 있다는건데 그럼 어떻게 해야하지?

라고 생각하며 이리 저리 그려보다가 '육각형'에서 힌트를 얻어 아래와 같이 그려봤다

그러니깐 1을 중심으로 주변의 테두리에 선을 그어서 나무의 나이테 처럼 나눠보았다.

그리고 중심점을 1, 두번째 테두리를 2, 나머지도 3, 4, 5... 이렇게 그려나가니깐 윤곽이 보였다.

또 예제에서 주어진 13과 58의 위치도 정확히 들어맞았다.

그러니깐 중심을 기준으로 6개의 블럭이 주위를 애워싸고, 그 2배인 12개의 블록이 다시 한번 둘러싸인 형태이다.

즉, 6 * n 의 형태를 띄고 있다는 사실을 알았다.

이제 이걸 코드로 작성하면...

import java.util.Scanner;

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

        int sum = 1;
        int count = 1;

        while(true) {
            if(n <= sum){
                System.out.println(count);
                break;
            }
            sum += 6 * count;
            count++;
        }

    }
}

count와 sum은 초기값 1이고, 한번 비교를 할때마다 sum은 6의 배수로 늘어난다.

이렇게 또 한 문제를 풀어냈다.