choiking10   8달 전

반드시 1을 포함하고 있기 때문에 이렇게 풀면 된다고 생각했는데 


오답이 뜨네요. 무슨 문젤까요?

draner11   8달 전

간단하게 생각하면 


1   4  5 7 원이있을때 10원을 만드는 방법이라면.  7 + 1, 1, 1 총 4개로 최소인데
5 5 가 최소가 되서 2개가 됩니다.

DP나 stack을 이용해서 푸시는게 맞다고 생각합니다. 

choiking10   8달 전

아 ㅋㅋㅋㅋㅋㅋㅋ 감사합니다.

draner11   8달 전

제가 문제를 이제 읽어봤는데 일반적인 방법으론 안될거같네요.

dp나 stack을 쓰려면 저 큰돈을 가지고있는 bool type 배열이 필요한데.


최소 1000mb가 필요합니다. 10^9 / 10^6 . 

그러면 이걸 따로 저장할 배열이 필요하게되네요. bool visit[~~~];


3원 과 1원이 있다고 치면.


3원 - > 3, 4, 1 원 -> 3 4 1  6 7 4  (3중복 처리)

이런느낌이야합니다.  그래서 이전에 숫자가 나왔는지를 체크하기위해서 

메모리 때문에 않되니.. 체크 배열을 만들어놓고. 3 4 1 넣고 다음에 3 4 1 6 7 4 넣고 넣기전에 이 배열안에 있었니?

라고 찾아야할 듯합니다. 그런데 여기서  체크배열이 길어지면 찾는데 시간이 소요겠네요.. 그래서 저라면 hash 개념을 써서.

100이면

visit[2][1000] = {  } 이런식에다가 2번쨰 10^2승이니 넣고 검사할듯합니다.

10 ^18승이니 [18][???] 만큼이네요.. 


풀어보진 않아서 잘 모르겠으나... 그냥 이론은 이런듯합니다...

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