IT Docs

문제 링크 : https://www.acmicpc.net/problem/13305
문제 등급 : Silver IV

문제 해결 로직

1. 리터당 가격을 기준으로 반복문을 돌린다.
2. 이전 리터의 가격과 현재 리터의 가격을 비교하여 작은 값을 기록한다.
3. 작은 값으로 거리와 곱해 주유 비용을 계산한다.

위의 로직을 보면 매우 간단하다.

하지만 처음 문제를 풀었을 때 17점을 받았었다.

간단히 공유하자면

1. 이전 도시에서 주유한 주유비와 현재 도시의 주유 비와 앞으로 갈 전체 거리를 계산하여 기록하였다.

2. 이전의 주유비와 비교하여 작은 값을 기록하였다.

3. 앞으로 간 거리만큼 전체 거리에서 빼주고 이전 도시에서 주유한 주유비를 기록하였다.

long tot = Integer.MAX_VALUE, stat = 0;

for(int i = 0; i < dis.length; i++) {
  long d = dis[i];
  long a = Long.parseLong(amounts[i]);
  tot = Math.min(tot, stat + (a * totDis));
  totDis -= d;
  stat += (a * d);
}

위의 1~3번을 반복하면 가장 작은 값의 주유비가 나온다 하지만 값이 너무 커질 수 있다.

BigInteger로 구현해도 17점이였다. 

차이점은 틀린 로직에서 불필요한 계산이 들어가는것 밖에 없었는데 17점을 받았다.

메모리나 시간상의 문제도 없었다.

왜 틀렸는지 의문이지만 해결된 로직이 더 간결하긴하다...

아래와 같이 해결 로직의 소스를 공유합니다.

public class 주유소 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        br.readLine();

        String[] dis = br.readLine().split(" ");
        String[] amounts = br.readLine().split(" ");

        long min = Long.parseLong(amounts[0]), tot = 0;
        
        for (int i = 0; i < dis.length; i++) {
            long d = Long.parseLong(dis[i]);
            long a = Long.parseLong(amounts[i]);

            if(a < min) min = a;

            tot += (min * d);
        }

        System.out.println(tot);
    }
}

문제 링크 : https://www.acmicpc.net/problem/1339
문제 등급 : Gold IV

입력

2
GCF
ACDEB

문제 해결 로직

1. 알파벳이 들어갈 배열 생성
2. 각 문자열의 알파벳을 문자형으로 받고 배열의 해당 문자의 위치에 자릿수를 삽입한다.
   1. A의 경우 'A'를 뺄셈 하여 0번을 받는다.
   2. A의 위치의 값이 0이 아니면 A의 값과 더해주고 값이 0이라면 A에 값을 삽입한다.
   3. 위와 같이 자릿수를 구하면 A = 10000, C = 1000, D = 100, E = 10, B = 1, G = 100, C = 10, F = 1과 같이 자릿수를 구할수 있다.
   4. C의 경우 앞에서 1000 넣어 최종적으로 C = 1010이 된다.
3. 자리수를 구한 배열을 내림 차순으로 정렬한다.
4. 정렬된 배열에서 가장 큰 값인 9부터 0까지 배열의 요소와 곱한다.
5. 반복문을 돌면서 최대 값을 구한다.

이 문제를 분석했을 때 전체 탐색으로 풀려고 하였다. 하지만 전체 탐색으로 푸는 법도 막막하여 풀이를 찾아보았다.

전체 탐색하면 시간 초과가 발생하여 전체 탐색을 하지 않고 자릿수를 구해 최댓값을 구하는 풀이를 보았다.

이 문제는 아주 그리디스러운 문제라는 걸 느꼈다.

아래와 같이 소스를 공유합니다.

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

        int n = sc.nextInt();

        int[] ap = new int[26];

        for(int i = 0; i < n; i++) {
            char[] str = sc.next().toCharArray();

            for (int j = 0; j < str.length; j++) {
                int pow = (int) Math.pow(10, str.length - j - 1);
                char c = str[j];
                int s = str[j] - 'A';
                if(ap[s] != 0){
                    ap[s] += pow;
                }else {
                    ap[s] = pow;
                }
            }
        }

        int sum = 0;
        
        // 0 제거 후 내림차순으로 정렬
        List<Integer> list = Arrays.stream(ap).boxed().filter((item) -> item != 0).sorted(Collections.reverseOrder()).collect(Collectors.toList());

        for(int i = 0; i < list.size(); i++) {
            sum += list.get(i) * (9 - i);
        }

        System.out.println(sum);
    }
}

문제 링크 : https://www.acmicpc.net/problem/1789
문제 등급 : Silver V

문제 해결 로직

1. 찾고자 하는 값보다 클 때까지 1부터 n까지 더하면서 count 한다.
2. count - 1을 하여 더한 개수를 구한다.
   1. n이 20일 때, 1, 2, 3, 4, 5, 6으로 21을 구한다.
   2. count는 6이 된다.
   3. 하지만 n과 21은 다르기 때문에 하나의 값을 빼주어야 하는데 n과 21의 차가 더한 값에 있음으로 count에서 1을 빼준다.

이 문제를 보고 백트래킹으로 문제를 풀려고 하였다. 하지만 너무 깊게 생각했다.

너무 오랜 시간 붙잡고 있어도 오기일뿐 효율이 안 나기 때문에 문제의 풀이를 보았다.

문제의 풀이를 보고 무릎을 탁 쳤다.

전혀 생각해보지 못한 풀이였다.

아래와 같이 소스를 공유합니다.

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

        long n = sc.nextLong();
        long sum = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if(sum > n) break;
            sum += i;
            cnt++;
        }

        System.out.println(cnt-1);
    }
}

문제 링크 : https://www.acmicpc.net/problem/1946
문제 등급 : Silver I

문제 해결 로직

1. 서류 순위와 면접 순위 중 서류 순위를 기준으로 오름차순으로 정렬한다.
2. 첫 번째 면접자는 서류 순위 중 1등이기 때문에 합격이다.
3. 첫 번째 면접자의 면접 순위를 기준으로 면접 순위가 작은 면접자를 찾아 합격시킨다.
4. 면접 순위가 작은 면접자를 기준으로 보다 작은 면접 순위를 가진 면접자를 합격시킨다.
5. 4번을 반복하여 합격자의 수를 카운트한다.

이 문제의 핵심은 문제를 잘 읽고 해석하는 것이었다.

다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙에서 많이 헷갈렸다.

처음에는 서류 순위 기준으로 정렬 후 바로 다음 지원자와 비교하여 합격을 판단하였다.

하지만 잘 못된 로직이었고 합격한 사람을 기준으로 더 나은 성적을 가진 지원자가 합격하는 것이었다.

구현 자체는 어렵지 않았으나 문제를 해석하는 게 어려웠다.

아래와 같이 소스를 공유드립니다.

public class 신입사원 {
    public static class Node {
        int g1, g2, sum;
        Node(int g1, int g2, int sum) {
            this.g1 = g1;
            this.g2 = g2;
            this.sum = sum;
        }
    }
    public static Comparator<Node> compare = new Comparator<>() {
        @Override
        public int compare(Node o1, Node o2) {
            return Integer.compare(o1.g1, o2.g1);
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            int t = Integer.parseInt(br.readLine());
            List<Node> list = new ArrayList<>();
            for (int j = 0; j < t; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                int g1 = Integer.parseInt(st.nextToken());
                int g2 = Integer.parseInt(st.nextToken());
                list.add(new Node(g1, g2, g1+g2));
            }

            list.sort(compare);

            int cnt = 1;
            int c = list.get(0).g2;
            for (int j = 1; j < list.size(); j++) {
                if(c > list.get(j).g2) {
                    cnt++;
                    c = list.get(j).g2;
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.println(sb.toString());
    }
}