9938번
9938번 - 방 청소 이동할 수 있는 서랍을 parent 와 child 관계로 묶으면서 문제를 풀 수 있었다. 그리고 각 서랍이 술병이 들어있는지를 full 배열을 통해서 나타냈다. 규칙 3,4번을 어떻게 나타내야 할까 하다가, 끝까지 가보지 않더라도 find 함수를 통해, 제일 root값을 찾았을 때, 그 서랍이 비어있으면 규칙을 만족하므로, 다시 parent 를 재정의 하면서 문제를 풀 수 있었다. 처음에 술병을 이동시켜서 서랍을 바꿔주면, parent 와 child 관계를 일일이 거꾸로 표현을 어떻게 해야할지 고민했다. 그런데 조금 생각해보니까, root 만 바꿔주면, 모든 관계가 거꾸로 표현할 수 있다는 것을 깨달았다.. 또 문제가 되었던 점은, 처음에 merge 함수를 쓰지 않고, 그냥 p[x..
더보기
1398번
1398번 - 동전 동전을 최소개수로 사용하는 방법을 찾는 문제. 그리디 문제에서 많이 나오지만, 만약 동전이 배수를 이루지 않는다면, 그리디 방식으로 풀 수 없다. 그래서 동전을 써가면서 규칙을 찾아봤다. 일단 가장 큰 가치를 가지는 동전을 써야한다는 기본 베이스는 똑같이 시작했다. 25 * 100^k , 100이라는 값에 주목했다. 이는, 숫자의 길이가 짝수 일 때 사용해야 이익을 볼 수 있다는 생각을 떠올렸다. 만약 125원을 만들려면, 100원1개,10원2개,1원5개 or 25원 5개 or 100원1개,25원1개.. 결국 25 * 100^k 은 짝수일 때 사용할 수 밖에 없다, 홀수 길이일 때 사용하면 오히려 손해가 발생한다. 그래서 10^k 로 모두 구해보면서 ,짝수일때만 25*100^k 의 동..
더보기
1614번
1614번 - 영식이의 손가락 이 문제는 규칙성을 파악해서 풀 수 있었다. 일단 손가락을 쓰는 순서가 1-2-3-4-5-4-3-2-1-2-3-4-5-4-3-2-1-.... 이런식으로 반복이 되는데 밑줄 친 부분이 반복이 일어난다. 이를 통해서 숫자를 구할 수 있다. 일단 저 8개에서 1과 5는 1번, 2,3,4는 2번이 나오게 된다. 일단 1은 0번째 다음에 나오고, 2는 1번째,7번째 다음에 나오고, 3은 2번째,6번째 다음에 나오고, 4는 3번째,5번째 다음에 나오고, 5는 4번째 다음에 나오게 된다. 이 모든 값을 plus 배열에 저장하였다. 값을 구하는 방법은 2를 3번 사용할 때는 동일부분 1번 반복하고(그러면 2를 두번 사용), 그 다음에 두번째에 있는 2의 앞의 갯수(7번째)까지 더해주면 된..
더보기