[백준온라인저지 1532 : 동전교환 ]
풀긴 풀었는데 맞게 푼건가... 싶은 문제 혹시 누군가 이 글을 보게 된다면 더 쉬운 풀이
혹은 더 좋은 방법을 알려줬으면 좋겠다.ㅜㅠ
일단 문제는 G1,S1,B1 개의 금화, 은화, 동화를 가지고 있는데 G2,S2,B2개로 교환하려고한다.
이때 최소 몇번 만에 교환을 할 수 있는가?
교환 종류는
금 1개는 은 9개
은 11개는 금 1개
은 1개는 동9개
동 11개는 은 1개
이렇게 4종류만 된다.
BFS로 풀어야 된다고는 생각했는데 메모리가 터져버리거나 시간이 초과되서
단순 BFS는 안되었다..
그래서 초반에 계산으로 가능한 부분들을 최대한 처리해버리기로 했다.
필요한 은화 갯수를 먼저 금으로 최대한 충당시켰다.
그리고 필요한 동화 갯수를 은으로 최대한 충당시켰다.
이 후에 남은 금 갯수를 은으로 최대한 바꾸면서
이 과정에서 S1이 S2보다 작을때까지 계속 동화로 바꾸었다.
이러한 일련의 과정들에서 G1,S1,B1이 G2,S2,B2와 같으면 바로 답을 출력하도록했다.
그후에 현재 G1,S1,B1을 큐에넣고 BFS를 돌렸는데
이미 전처리 과정을 심하게 거쳐서인지 BFS 몇번 돌지도 않고 끝나버렸다.ㅋㅋ.
이문제 정말 10번 넘게 틀렸는데 스트레스 받았었다..
-
1차를 붙고 드디어 2차!!! 솔직히 조금은 기대하고 시험을 봤다. 뭔가 처음 대회에 본선까지 가버리는 건 아닌가~? 하면서 역시 말도안되는 생각이었고 아마도 2차예선에서 떨어질것 같다!! ㅎㅎ 이번 결과는 !!! 1번은 풀고 2,3 번... -
[백준온라인저지 1532 : 동전교환 ] 풀긴 풀었는데 맞게 푼건가... 싶은 문제 혹시 누군가 이 글을 보게 된다면 더 쉬운 풀이 혹은 더 좋은 방법을 알려줬으면 좋겠다.ㅜㅠ 일단 문제는 G1,S1,B1 개의 금화, 은화, 동화를 가지고...
-
[ 백준 5549 : 행성 탐사 ] 백준에 기본 DP문제 중 [백준 11660 : 구간 합 구하기 5 ] 이 문제와 똑같은문제입니다. (A,B)~(C,D)의 직사각형안에 있는 J와 O와 I의 갯수를 뽑아야합니다. 한 좌표마다 그 전 ...
-1 가 답으로 나오는 경우 처리는 어떻게 해줘야 되나요?
답글삭제