juhongkim2   2년 전

"문제에 M개의 블루레이에 모두 녹음하려했다" 고 되어있어서

처음엔 딱 M개 일때만 정답을 찾아주도록 작성했었는데 틀렸다 해서

혹시 M개 이하로 녹화해도 되는건가 싶어서 코드를 바꿔봤더니 정답처리되네요...


딱 M개가 되도록 해야하는건지

M개 이하로 해도 되는건지 헷갈리는데 제가 문제조건을 제대로 이해 못한건가요?

아니면 조건이 부실하게 명시되어있는건가요?

chogahui05   2년 전

그러면, 이걸 어떻게 접근해야 할까요?

일단, 다른 분들도 거의 이런 식으로 푸셨을 거라 생각합니다.


블루레이에 넣을 수 있는 용량 = M 이라고 하면, 최대한 앞에서부터 넣어 보자!!

그랬을 때, 필요한 최소의 블루레이 갯수를 m이라 합시다.


(넣을 수 있는 만큼 넣은 것 1) (넣을 수 있는 만큼 넣은 것 2) (넣을 수 있는 만큼 넣은 것 3) ... (넣을 수 있는 만큼 넣은 것 m)

이렇게 되겠죠. 여기까지는 누구도 부정을 못 하는 사실입니다. 당연히, m개보다 적은 블루레이에는 못 넣겠지요.


당연한 이야기겠지만, 넣을 수 있는 만큼 블루레이에 넣은 노래들 길이의 총 합은 M을 넘어가지 않습니다.

푸셨으니 잘 아실 거라 생각합니다.


여기서 생각을 더 해 봅시다. 넣을 수 있을 만큼 넣은 블루레이를 쪼갠다고 생각해 봅시다. 1개던, 2개던, 3개던.

물론 블루레이의 길이는 M으로 같게 말이죠.


(넣을 수 있는 넣은 것 1)의 아이템 갯수를 x라고 합시다. 그러면 이건 최대 x개로 쪼갤 수 있을 겁니다.

(길이가 M이고 넣을 수 있는 만큼 넣은 것 1의 아이템 1만 넣은 것) 

(길이가 M이고 넣을 수 있는 만큼 넣은 것 1의 아이템 2만 넣은 것)

...

(길이가 M이고 넣을 수 있는 만큼 넣은 것 1의 아이템 x만 넣은 것)


맞나요?

이런 모든 경우에 대해서 해 보면

블루레이의 길이가 M이고, 이 경우에 필요한 최소 블루 레이의 갯수를 m이라고 하면

블루레이 길이가 M인 블루레이에, m보다 크거나 같고, 노래의 총 갯수보다 적은, 길이가 M짜리인 블루 레이에 넣을 수 있다!!

는 것이지요.


노래의 총 갯수만큼의, 길이가 M짜리인 블루 레이에 넣을 수 있는 경우는 어떤 경우일까요?

당연히 노래 1개씩을 넣는 경우겠지요. 물론 자원 낭비겠지만요.

그래도 이해가 안 되시면 추가 덧글 부탁드립니다~

chogahui05   2년 전

ps.

(1) 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안된다.

(2) 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 

(3) 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 레슨 동영상을 녹화하기로 했다.

(4) 이 때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

(5) 이 때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.


여기서 (3)이 잘 이해가 안 가셨지요? 저도 그랬습니다. 근데 이건

귀납적인 증명을 천천히 해 보시면 이해가 가실 겁니다. 이걸 간파하시는 게 핵심이지만요.

juhongkim2   2년 전

답변 감사합니다

문제 의도를 정확히 파악하는것도 실력인데 전 아직 많이 부족하네요ㅠ

댓글을 작성하려면 로그인해야 합니다.