백준 16678번: 모독 (Python/Java)

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

16678번: 모독

 

 

 

접근

---

연쇄작용이 있다는 것이 중요한 문제. 일단 한 명이라도 명예 점수가 0이 나온 상태가 계속 이어지면 반복해서 국회의원들을 없앨 수 있다. 이 얘기는 무엇이냐, 바로 1부터 가장 큰 수까지 1씩 차이나는 숫자 조합이 만들어져야 한다는 뜻이다. 그래야 -1을 할 때마다 명예점수가 0인 국회의원이 계속 나오고, 한 번의 Defile을 통해 모든 국회의원을 연쇄적으로 없앨 수 있게 된다.

 

우선 배열을 순서대로 정렬해준다. 오름차순, 내림차순 둘 다 상관은 없겠다만 나는 편의상 오름차순으로 정렬했다. 그 뒤, 가장 작은 숫자가 1인지 확인한다. 1부터 가장 큰 수까지 1씩 차이가 나야 한다는 말은 가장 작은 숫자가 1이어야 한다는 말과 같기 때문이다. 그 뒤, 배열의 바로 전 숫자와 현재 숫자를 비교해서 숫자가 크다면 바로 직전 숫자보다 1만큼 더 큰 숫자로 바꿔주면 된다. 작다면 굳이 바꿔줄 필요가 없다. 1부터 1씩 증가시켜주면서 변환시켜줬기 때문에 직전 숫자보다 작다면 굳이 바꿔주지 않더라도 증가 범위 안에 들어가는 숫자이기 때문이다.

 

 

 

풀이

---

Python

allNum = int(input())

board = [0 for i in range(allNum)]
for i in range(allNum):
    board[i] = int(input())

board = sorted(board)

result = 0
if board[0] != 1:
    result += (board[0]-1)
    board[0] = 1

for i in range(1, allNum):
    if board[i-1] < board[i]:
        result += board[i] - (board[i-1]+1)
        board[i] = board[i-1]+1

print(result)

 

Java

import java.util.Arrays;
import java.util.Scanner;

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

            int allNum = Integer.parseInt(scan.nextLine());

            Integer[] board = new Integer[allNum];
            for(int i = 0 ; i < allNum ; i++){
                board[i] = Integer.parseInt(scan.nextLine());
            }

            Arrays.sort(board);

            long result = 0;
            if(board[0] != 1){
                result += (board[0] - 1);
                board[0] = 1;
            }
            
            for(int i = 1 ; i < allNum ; i++){
                if(board[i-1] < board[i]){
                    result += (board[i] - (board[i-1]+1));
                    board[i] = (board[i-1]+1);
                }
            }

            System.out.println(result);

        }

}

 

 

 

후기

---

지금껏 2~3주 정도 그리디 알고리즘을 풀면서 풀이 방법을 가장 헤맸던 문제이지 않나 싶다. 처음에는 위 해설처럼 푼 것이 아니라  입력 숫자들 중에서 1부터 1씩 증가시키며 해당 숫자가 있는지 하나하나 찾아보고 없는 숫자들을 배열로 만들었다. 이를 다시 for문을 돌려 입력 숫자 중 큰 숫자들부터 해당 배열의 숫자로 만들어가는 방식으로 풀었다. 지금 생각해보니 굉장히 1차원적인 발상이었다. 코드도 길고 복잡해졌고 무엇보다 일단 채점을 돌려보면 틀렸다.

 

이는 코드 구현의 문제가 아니라 그리디 알고리즘에서 가장 중요한 '현재 최적 방법'을 제대로 생각해내지 못했다는 얘기가 됐다. 그리디 알고리즘 문제를 풀 때에는 최적 방법 제대로 생각해내기, 끝까지 잊지 않도록 해야겠다.