작은 기록공간

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의 배수로 늘어난다.

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

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

이 문제는 부분합을 구하는 문제인데,

알고리즘을 보니 브루트포스 알고리즘으로 분류되어 있어서 정말 무식하게 풀었다...

내가 생각한 건 1부터 주어진 수까지 1씩 값을 증가시키면서 숫자를 한 자리씩 분리해서 더했다

여기서 num/2를 한 이유는 범위를 반 정도라도 줄이기 위해서 사용했다.

import java.util.Scanner;

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

        // i 부터 num 까지 반복
        for (int i = num/2; i < num; i++) {
            // 자릿수 더하기
            for (int j = 0; j < String.valueOf(i).length(); j++){
                // i번째 숫자를 한자리씩 분해하여 정수형으로 바꾼 다음 sum에 더함
                sum += Character.getNumericValue(String.valueOf(i).charAt(j));
            }
            sum += i;

            if(sum == num) {
                result = i;
                break;
            }
            // 초기화
            sum = 0;

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

정말 끔찍하게 풀었지만 일단 맞긴했다;;

아마 브루트포스 알고리즘이 아니었으면 바로 틀렸을 것 같다.

여기서 더 개선할 수 있는 방법을 생각해 보면

1. 뒷자리 수부터 차례로 내려간다

2. 자릿수 분해를 문자열로 나누는 게 아니고 산술연산으로 나눈다.

이 정도가 생각난다.

그래서 한번 Copilot 한테 내 코드의 문제점과 가장 좋은 설루션이 뭐가 있냐고 물어봤다.

이 문제는 분해합 (Decomposition Sum)에 관한 문제로, 문제의 입력 숫자 N에 대한 생성자 M을 찾는 것입니다.

주어진 해결 방법은 전체 숫자를 순차적으로 검사하므로 시간복잡도가 높다는 단점이 있습니다. 이를 개선할 수 있는 방법을 제안드릴게요.

더 나은 방법
실제로 이 문제를 해결하는 더 좋은 방법은 역시 브루트포스를 사용하는 것이지만, 모든 숫자를 다 검사할 필요는 없습니다. 다음의 방법으로 계산을 줄일 수 있습니다:

1. 최소 탐색 범위 설정:
   - 보통 생성자의 범위는 N - 9\*자릿수 정도로 한정할 수 있습니다. 예를 들어, 입력 숫자가 100이라면, 100 - 9\*3 = 73부터 시작할 수 있습니다. 이는 각 자리 숫자가 9인 최대 경우의 수를 고려한 것입니다.

2. 생성자 계산:
   - 각각의 숫자에 대해서 각 자리의 숫자 합을 구하고 이를 더해 나갑니다. 이를 통해 분해합을 계산합니다.

다음은 개선된 코드 예제입니다:

import java.util.Scanner;

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

        for (int i = Math.max(1, num - 9 * String.valueOf(num).length()); i < num; i++) {
            int sum = i;
            int temp = i;
            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }

            if (sum == num) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

설명
- 범위 설정: `num - 9 * String.valueOf(num). length()`를 이용해 최소 탐색 범위를 설정합니다.

                    예를 들어, `100`인 경우 `100 - 9*3 = 73`부터 시작합니다.
- 생성자 계산: `i`의 각 자릿수를 더하는 방식으로 분해합을 계산합니다.

이렇게 하면 불필요한 계산을 줄여 성능을 개선할 수 있습니다. 이 방법을 사용하면 좀 더 효율적으로 문제를 해결할 수 있을 거예요. Happy coding! 🎉

솔직히 범위를 저렇게 까지 줄일 수 있을 줄은 생각도 못했다.

for문에 대한 설명을 조금 더 자세히 물어봤는데

1. String.valueOf(num). length() : 

num을 문자열로 변환하여 길이(자릿수)를 구하고,

2. num - 9 * String.valueOf(num). length():

탐색의 최소 범위를 설정하기 위해서 num에

1의 자리 숫자 중에 가장 큰 9를 자릿수와 곱한 값을 뺀다.

예를 들어, num이 100이라면, 100 - 9 * 3 = 73이 된다.

3. Math.max(1, num - 9 * String.valueOf(num). length()):

음수를 피하기 위해서  1보다 작다면 1을 반환한다.

정말 죽었다 깨어나도 이렇게 생각하진 못했을 것 같다

다음으로 while문에서는

while (temp > 0): temp가 0보다 클 때까지 반복합니다.

• sum += temp % 10: temp의 마지막 자릿수를 sum에 더합니다.
• temp /= 10: temp를 10으로 나누어 마지막 자릿수를 제거합니다.

이렇게 자릿수를 더하고 그 결과를 입력받은 값과 비교에서 같으면 반복문을 종료하고 출력한다.

정말 여러모로 많이 배울 수 있는 시간이었다.