방구석프로의 이야기

www.acmicpc.net/problem/1475

문제 해결을 위한 과정

이 문제의 키 포인트는 9와 6이 서로 뒤집을 수 있다는 것입니다. 그 숫자들을 제외하고는 숫자의 개수만큼 세트의 개수가 증가하기 때문에 고려하기 쉽습니다. 따라서 0부터 9까지 0으로 초기화된 리스트를 선언하고 6, 9는 더 작은 인덱스 번째를 증가시켜주고 그 외의 숫자는 해당 인덱스의 값을 증가시켜주는 방법을 통하면 쉽게 계산할 수 있습니다.

35996가 입력으로 주어진다고 가정하면 3번째 인덱스 5번째 인덱스의 값을 각각 증가시킵니다. 이를 그림으로 표현하면 다음과 같습니다.

초기 상태

3번째와 5번째를 하나씩 증가시킨 후

9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 인덱스를 증가시킴 편의상 낮은 인덱스를 증가시킴

9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 9번째 인덱스를 증가시킴 

6이 왔으므로 6번째 인덱스와 9번째 인덱스 중 더 작은 값을 가지는 6번째 인덱스를 증가시킴

이렇게 각 인덱스를 증가시키는 과정이 끝난 후 리스트에서 최댓값을 출력하면 필요한 세트의 수가 나오는 것을 알 수 있다.

소스코드