32비트 컴퓨터 납품하기

시작해보며

매주마다 하나씩 문제를 정의하고, 답안을 해설한 글을 만들어볼 생각입니다. 첫 문제로 브루트 포스 기반의 순열-조합 응용 문제를 만들어봤습니다.

문제

x86 inc.은 32비트 컴퓨터를 전문적으로 납품하는 업체이다. 날이 갈수록 32비트 프로세서를 찾기 어려워지는 상황이라 64비트 CPU를 대체제로 사용한다고 한다. (물론 운영체제는 여전히 32비트이다) 또한, 새로운 선택 사항으로 SSD를 넣었다.

64비트와 HDD를 같이 공급할 경우 비용은 2이고, 여기서 HDD를 SSD로 바뀔 경우 경우 비용은 4이다. 참고로 지난 컴퓨터 라인업의 비용은 1이고, 재고가 아직 남아 있어 이번 라인업 이윤 계산에 포함한다. 그래서 32비트 + SSD는 개당 공급 비용을 3으로 갖는다.

x86 inc.의 사장은 가능한 한 공급 횟수를 적게 들여 주어진 예산 R을 가장 먼저 사용하는 조합을 궁금해 하였다.

주어진 예산 M를 지키면서, 시전순으로 먼저 오는 조합을 아래 형식으로 출력한다.

M의 범위는 5 <= N <= 1000까지 가능하다.

입력과 출력 예

입력 1

5

츨력 1

1
0
0
1

입력 2

10

출력 2

0
1
0
2

입력 3

367

출력 3

0
0
1
91

해설

이 문제는 {1, 2, 3, 4}를 중복하여 M개 이하를 선택하는 것으로, 이때 가장 적게 선택한 순열의 합이 M이 되도록 한다. 순열의 순서를 섞어도 결과 값은 다르지 않은 조합의 경우이다.

그런데 {1, 2, 3, 4}를 중복하여 M개 이하를 선택한 순열의 합이 M에 만족하지 않은 경우가 있을 것이다. 이 문제의 요점은 최대한 적은 횟수로 M을 만들어내는 것이고, M이 적어도 5라는 경우가 주어졌다. 따라서 집합의 가장 큰 수인 4를 가능한 한 많이 사용하여 이 문제를 푸는 것이 합리적이다. 아마도 x86 inc. 사장의 큰 그림인 것 같다(?)

하지만 사전 순으로 먼저가 되는 순서를 골라야 되므로 무질서하게 4를 많이 써서 해결할 수는 없다. 따라서 집합 {1, 2, 3, 4}의 사전식 N-수열(N<=M)에서 N의 범위를 M/4를 반올림 한 값과, 최대 범위로 M/2으로 된 근삿값을 사이로 정하여 합이 M에 만족하는 경우가 적어도 하나는 있게 최적화를 할 수 있다.

순열의 순서를 섞어도 합이 바뀌지 않아 중복을 제거할 필요성이 있지만 이미 만들어 낸 사전식 순열에서 중복된 경우를 제거하는 것은 낭비가 심하다. 따라서 비 내림차순을 바탕으로 순열의 합을 계산하여 M과 비교하는 것이 가장 단순한 접근 방법일 것이다.

정리하자면 아래와 같다.

  1. {1, 2, 3, 4}의 N-비내림차순 순열 생성
  2. N의 범위는 M/4 (반올림) <= N < M/2

아래부터 입출력 예를 적어뒀다.

구현체

BOJ#1562 N과 M (4) 답안을 응용하여 풀 수 있었다.