블로그 언저리인 무언가

문제 : 4811 알약 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 매일매일 알약을 꺼내먹었을 때, 전체 조각과 반 조각을 뽑는 순서의 경우의 수를 세 출력하는 문제이다. 남은 알약이 모두 반 조각 짜리라면 문자열이 결정되고, 반 조각짜리 알약이 음수 개인 경우는 불가능하게 처리하여 memoization기법을 활용해 Top-Down 방식의 DP를 짜서 이전 결과 값을 저장해 꺼내서 출력했다. Code #include #define ll long long using namespace std; ll N, M, arr[35][..

문제 : 13703 물벼룩의 생존확률 13703번: 물벼룩의 생존확률 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 www.acmicpc.net 1초마다 1/2 확률로 위 또는 아래로 이동할 때, 시간이 끝날 때까지 생존해있는 경우의 수를 구하면 된다. 수면에 닿았을 때 남은 움직임과 상관없이 모두 실패하고 남은 움직임 횟수보다 더 깊이 있는 상태에서는 2^횟수만큼 성공하므로 memoization기법을 활용해 Top-Down 방식의 DP를 짜서 이전 결과 값을 저장해 꺼내서 출력했다. Code #include #define ll long long using na..

문제 : 4386 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일� www.acmicpc.net 별들의 좌표가 주어졌을 때 각 별들을 모두 잇는 최소 길이를 구해 출력하는 문제이다. 최소 스패닝 트리를 구해야 하므로 UnionFind를 짜고 각 간선에 이어진 점과 간선의 비용을 우선순위 큐에 넣어 가장 적은 비용부터 꺼내며 사이클이 생기지 않게 처리해주면 된다. Code #include #define ll long long using namespace std; typedef pair pdd; struct ABC{ ll a, ..

문제 : 14890 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 지도가 주어졌을 때, 가로, 세로로 경사로를 놓으며 길을 만들어 지나갈 수 있는 길의 수를 출력하는 문제이다. 모든 가로세로를 확인하면서 높이가 같다면 길이를 늘리고 올라가는 경사로나 내려가는 경사로를 세울 때 지을 수 있다면 길이를 줄인다. 길의 끝까지 왔을 때 길이가 음수이거나 도중에 경사로를 놓는 것이 불가능한 상황이 나오면 세지 않는다. Code #include #define ll long long using namespace std; ll N, M, ..

문제 : 1057 토너먼트 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 토너먼트 1라운드에서 번호가 주어졌을때, 두 참가자가 몇라운드에서 만나는지를 출력하면 되는지 문제이다. 번호를 1번이 아닌 0번부터 생각해보면 만나는 사람은 2로 나눴을때의 몫이 같으므로 같을때까지 반복해주면 된다. Code #include #define ll long long using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); ll N, a, b, ans=1; cin ..

문제 : 14889 스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 짝수인 수의 사람이 주어졌을 때, 절반으로 나눠 각 팀 능력치 합의 차이가 최소일 때 그 값을 출력하는 문제이다. next_permutation을 사용해 모든 경우의 수를 구하고 각 경우의 능력치 차이를 구해 최솟값을 갱신한 후 출력하면 된다. Code #include #define ll long long #define INF 987654321 using namespace std; int main(){ ios::sync_with_stdio(0); ci..

문제 : 10779 쇠막대기 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저� www.acmicpc.net 쇠막대와 레이저의 위치가 괄호로 주어졌을 때 잘린 막대기의 총개수를 출력하는 문제이다. '(' 괄호가 들어오면 겹쳐진 쇠막대기의 개수를 1개 늘리고 ')' 괄호가 들어오면 레이저 거나 막대가 끝이 난 것이므로 막대기의 개수를 줄이고 앞의 괄호를 판단해 레이저인지 체크한 후 1 더하거나 겹쳐진 막대의 개수만큼 더한다. Code #include #define ll long long using namespace std; int main(){ ios:..