zidane92   8달 전

input이 좀 커지면 브루트 포스 말고 다른 방법을 써야 할 것 같아 생각 하던 중 간단하게 dp로 풀었는데요

논리적으로 전혀 모순이 없는 것 같은데.. 허점이 있을까요? 채점 시 계속 틀리네요 ㅠㅠ

2*A부터 검사하는 이유는 A,B,C 단위로 배정하기 때문에 각 한개씩 배정하는 경우를 제외하고 가장 작은 수가 2*A라고 생각했기 때문입니다

조언 부탁드려요

pichulia   8달 전

N이 A나 B나 C의 배수일 때 오답을 출력하고 있습니다.

또한, 정답에 직접적인 영향을 주진 않겠지만.. 2*A가 C보다 작을 수 있다는 점을 놓치셨습니다.

zidane92   8달 전

N이 A나 B나 C의 배수라면 1을 출력하는게 맞지 않나요? 방을 한 종류만 사용해도 된다고 써있어서...

또한  2*A가 C보다 작더라도, 이 알고리즘에서 허점은 없지 않나요? 2*A부터 dp를 해도 허점은 없어 보이는데... ㅠㅠ

pichulia   8달 전

1) 데이터를 넣어서 답이 진짜로 1이 출력되는지 확인해보셨나요.

2) 2A < C 일 때 i-C 값이 음수가 되서 dp[i-C] 값을 읽을 때 음의 인덱스를 읽어들이게 됩니다. 현재는 dp배열이 301로 충분히 크게 고정되있어서 dp[-1]같은걸 해도 오답이 나오지 않고 의도한대로 돌아갈테지만 만약 dp배열이 N+1 등이였다면 음의 index 접근에 의해 오답이 나올 수 있게됩니다.

알고리즘이 문제가 없어도, 그 알고리즘을 구현한 코드는 문제가 있을 수 있습니다.

zidane92   8달 전

아... 딱하나 제가 오해했네요.. 문제가 좀 굉장히 헷갈릴 소지가 있긴하네요..ㅋㅋ

A,B,C,N이 크기순으로 들어올거라 생각했습니다. N이 더 작을 수 있다는 건 아예 상상을 안하고 있었네요... 대체 몇번을 틀린건지... ㅠㅠ

@pichulia 님 댓글 감사합니다.

음의 인덱스를 참조하지 않게 컨디션을 조정하고, A,B,C,N이 크기 순이라면, 2*A부터 dp를 시작해도 될 거 같긴 합니다.

수정해서 해결했습니다.. ㅠㅠ 너무 쉬운 문제였는데 너무 오래걸렸네요 ㅠㅠ

pichulia   8달 전

...?! 올려두신 코드에서 13번째 줄 코드 앞에 띄어쓰기 4개만 넣어주면 정답을 받습니다;;;

zidane92   8달 전

ㅋㅋㅋㅋ 앗 ㅋㅋㅋㅋ 그렇네요 감사합니다 역시 2*A부터 탐색하는건 맞는 방법이였습니다!

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