4Legs_Archives

문제 링크 : www.acmicpc.net/problem/2600 2600번: 구슬게임 첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개 의 정수 b1 , b2, b3 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다. www.acmicpc.net 개인적으로는 DP문제가 어려운 이유를 느낄 수 있었던 문제이다. 이 문제는 복잡하게 생각할수록 풀기 어렵고, DP의 개념 중 하나인 분할 정복을 잘 생각한다면 쉽게 풀 수 있는 문제이다. 양쪽 통에 구슬이 각각 x개, y개 들어있을 때, 현재 구슬을 꺼내야 하는 플레이어가 이기는 경우를 생각해 보자. 플레이어는 여러 가지 수를 둘 수 있다. 문제에서 제시된 예제의 경우만 해도 최대 6가..

문제 링크 : www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이� www.acmicpc.net DP와 Bitmask를 활용해 해결할 수 있는 문제이다. Bitmask에 대해서는 다음 링크에 설명해 두었다. 4legs-study.tistory.com/5 Bitmask 에 대해 [서론] 스위치 4개가 있다고 생각해 보자. 이 스위치가 각각 켜져 있거나, 꺼져 있는 경우를 나타내려면 어떻게 해야 할까? 단순하게 생각해 보면 각 스위치마다 켜져 있는지, 꺼져 있는지에 �� 4legs-study.tistory..

[서론] 스위치 4개가 있다고 생각해 보자. 이 스위치가 각각 켜져 있거나, 꺼져 있는 경우를 나타내려면 어떻게 해야 할까? 단순하게 생각해 보면 각 스위치마다 켜져 있는지, 꺼져 있는지에 대한 bool 값을 지정해 bool의 배열 형태로 나타내면 될 것이다. 하지만 스위치가 백만 개, 천만 개라면 어떻게 스위치들의 상태를 나타낼 수 있을까? 또한, 특정 스위치가 켜져 있는지 확인하려면 어떻게 해야 할까? 이런 경우에도 앞서 말한 4개의 스위치가 있는 상황처럼 bool 배열을 이용해서 확인할 수는 있지만, 차지하는 메모리가 너무 많고 비효율적이다. [개념] 전체 원소 집합 중, 각 원소들을 on/off 형태로 구분할 수 있을 때, 특정 원소들의 포함 여부를 한 번에 나타내고 싶은 경우 사용한다. 예를 들..

문제 링크 : www.acmicpc.net/problem/1082 1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파� www.acmicpc.net DP의 대표적 유형인 거스름돈 문제와 유사한 문제이다. 숫자를 구매하여 높은 숫자를 만드는 방법은 두 가지가 있다. 1. 자릿수가 높은 숫자를 만든다. (ex. 11111 > 9999) 2. 자릿수가 같다면, 값이 높은 숫자를 만든다. 따라서, "숫자를 많이 사는 것"을 1순위로, "높은 숫자를 사는 것"을 2순위로 두고 구매한다. 아래 코드에서 vector dp[n] 은 금액 n으로 구..