1789번, 3085번 - 브루트포스

실버 저티어 문제로 두문제를 풀었다.

1789 - 수들의 합

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

 

즉, 자연수 N보다 같거나 커질때까지 1부터 더해가는 문제이다.

쉬운 문제이기에 두가지 방법으로 풀어보았다.

1. 단순 반복문

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long S = sc.nextLong();
        int count = 0;
        int num = 1;
        while (S > 0) {
            S -= num++;
            count++;
        }
        if (S < 0) {
            count--;
        }
        System.out.println(count);
    }
}

 

2. 수열의 합 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long S = sc.nextLong();
        int num = 1;
        while (2 * S / num > num + 1) {
            num++;
        }
        if (2 * S / num < num + 1) {
            num--;
        }
        System.out.println(num);
    }
}

 

수열의 합이 더 빠를줄 알았지만, 근소하게 반복문이 더 빨랐다.

 

3085번 - 사탕 게임

상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

 

브루트포스 알고리즘을 이용해 푸는 문제였다.

결국 어떤 규칙보다는...

그냥 사탕을 옆칸 또는 밑칸의 사탕과 바꿔보고 바뀐 줄에서 몇 개의 사탕이 빠지는지 검사하는 문제이다.

나는 이 방법이 너무나 비효율적이라고 생각하고, 연속된 같은 색상의 사탕을 찾아 그 양옆을 바꿔보려 했다.

하지만 해당 과정을 코드로 나타내기에는 무리가 있었고, 시간이 정말 오래걸려서 다른 사람의 코드를 참고했다.

import java.util.*;

public class 사탕게임_3085번 {
    static int check(char[][] a) {
        int n = a.length;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int cnt = 1;
            for (int j = 1; j < n; j++) {
                if (a[i][j] == a[i][j - 1]) {
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt)
                    ans = cnt;
            }
            cnt = 1;
            for (int j = 1; j < n; j++) {
                if (a[j][i] == a[j - 1][i]) {
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt)
                    ans = cnt;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] a = new char[n][n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.next().toCharArray();
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j + 1 < n) {
                    char t = a[i][j];
                    a[i][j] = a[i][j + 1];
                    a[i][j + 1] = t;
                    int temp = check(a);
                    if (ans < temp)
                        ans = temp;
                    t = a[i][j];
                    a[i][j] = a[i][j + 1];
                    a[i][j + 1] = t;
                }
                if (i + 1 < n) {
                    char t = a[i][j];
                    a[i][j] = a[i + 1][j];
                    a[i + 1][j] = t;
                    int temp = check(a);
                    if (ans < temp)
                        ans = temp;
                    t = a[i][j];
                    a[i][j] = a[i + 1][j];
                    a[i + 1][j] = t;
                }
            }
        }
        System.out.println(ans);
    }
}

 

코드가 너무 복잡하게 나올때는 빨리 다른 방법을 모색하는게 더 좋은 방법이라고 생각한다.