[백준온라인저지 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번 넘게 틀렸는데 스트레스 받았었다..
-
[ 백준 1024 : 수열의 합 ] 간만에 푼 백준~ 쉬운 문제라고 생각하고 풀었는데 계속 틀려서 봤더니 예외 처리를 한 개 안해준것이 있었다. 만약 이 글을 보기전에 풀었을때 채점이 60%에서 자꾸 틀린다면 90%확률로 나와 같은 실수를 ...
-
[백준 1091 : 카드 섞기 ] 이 문제도 5달 전에 풀었다가 포기했었던 문제였나보다. 오늘 틀렸던 문제 다시풀기 중 풀게 되었다. 문제를 읽는데 헷갈려서 머리카락 한 10번은 쥐어짠듯. 아마 전에 풀었을때는 P배열이 각 카드가 최후에 ...
-
아마 나와 비슷한 나이대의 학생들은 대부분 대학에서 수업을 들으면서 꾸준하게 들었을 것 같다. 물론 내가 그래서 그렇다. 4차산업~ IT의 시대~ 빅데이터~ 데이터 마이닝~ 하지만 컴퓨터 관련 전공자가 아니고 더군다나 공학 계열 전공자가 아니라...
-1 가 답으로 나오는 경우 처리는 어떻게 해줘야 되나요?
답글삭제