4Legs_Archives

문제 링크 : www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net 보석의 개수가 최대 14개이므로, 어떤 보석을 주운 상태인지 비트마스크를 통해 나타낼 수 있음을 캐치하자. 보석이 있는 섬에 도착했을 때, 보석을 주운 후 다음 섬으로 이동할 수도 있고 줍지 않고 이동할 수 있다. 위와 같은 예제 그래프에서, 1번 노드에서 출발해 최대로 보석을 주웠을 때의 개수는 4이다. 경로는 다음과 같다. ① 1번 섬에서 보석을 줍지 않고 5번 섬으..

문제 링크 : www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 이전에 포스팅했던 BOJ 1176 섞기와 동일한 접근법을 가진다. 어떠한 수들로 순열을 만들었을 때, 그 수들의 순서와 관계없이 우리는 이어붙인 수의 나머지만 알 면 된다. X개의 수를 이어붙인 큰 수를 k로 나눈 나머지가 r이라면, 그 r에 새로운 수 하나를 붙인 다른 한 수에 대한 나머지가 곧 X + 1개의 수를 이어붙인 큰 수를 k로 나눈 나머지이기 때문이다. 즉 1, 3, 5번의 수를 (3, 1, 5)의 순서로 이어붙이거나 (5,..

문제 링크 : www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 이 문제를 DP로 풀기 위해 필요한 정보는 다음과 같다. ① 현재까지 그림을 산 사람들에 대한 정보 (한번 그림을 산 사람은 다시 살 수 없으므로) ② 마지막으로 그림을 산 사람 (다음에 살 사람의 가격은 마지막으로 산 사람에 의해 정해진다.) ③ 마지막으로 팔았을 때 그림의 가격 (다음에 살 사람은 이 가격 이상으로 사야 하기 때문) 따라서, 이 3가지 정보를 담은 3차원 dp 배열을 ..

문제 링크 : 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/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 형태로 구분할 수 있을 때, 특정 원소들의 포함 여부를 한 번에 나타내고 싶은 경우 사용한다. 예를 들..