4Legs_Archives

문제 링크 : https://www.acmicpc.net/problem/1176 1176번: 섞기 첫 줄에는 학생의 수 N(1 ≤ N ≤ 16)과 최소 넘어야할 키의 차이 값 K(1 ≤ K ≤ 3,400)가 주어진다. 다음 N개의 줄에는 학생들의 키가 순서대로 들어온다. 키는 25,000 이하인 자연수만 들어온다. www.acmicpc.net 분할 정복을 이용한 아이디어 캐치가 중요한 문제이다. 문제의 상황은 N명을 줄세울 때, 줄을 서는 각 학생들의 양 옆 학생들과의 키 차이를 K 초과로 만들고 싶은 상황이다. 가능한 모든 경우를 보려면 최대 경우의 수가 16!로, 무려 조 단위의 수이므로 불가능하다. N명을 줄 세우는 과정을 생각해보자. 지금까지 내가 몇 명을 세웠던 관계없이, 학생 한 명을 지금 세..

문제 링크 : 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..

문제 링크 : 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으로 구..