https://www.acmicpc.net/problem/25489시간 제한메모리 제한4초1536MB문제국렬이는 작년 여름에 사용하다 남은 전구 스트립을 이용해서 자신의 자취방에 있는 N개의 정점으로 이루어진 트리를 장식하려고 한다. 전구는 트리의 각 정점에 하나씩 설치되어 있다. i번째 정점에 붙어있는 전구는 전원을 넣었을 때 p_i의 확률로 켜진다. 그리고 전구에 여유가 넘치는 국렬이는 간선에 추가 전구를 하나씩 달았다. 이 추가 전구들은 연결된 두 정점에 설치된 전구들 중 하나만이 켜졌을 때 불이 켜진다. 추가로 국렬이는 Q번 특정 정점에 설치된 전구를 다른 전구로 바꿀 것이다. 각 시점별로 불이 들어오는 전구 개수의 기댓값을 구하여라. 입력첫 번째 줄에는 정점의 개수 N이 주어진다. (2 ≤ N ..

https://www.acmicpc.net/problem/22975시간 제한메모리 제한2초1024MB문제현욱이가 살고 있는 도시에는 N개의 빌딩이 있다. 빌딩은 전부 일렬로 세워져 있으며, 첫 번째 빌딩부터 차례대로 1번부터 N번까지 번호가 붙어 있다. 각 빌딩 사이의 간격은 모두 1로 동일하다. 여기서 i번째 빌딩의 높이를 Hi라고 할 때, 일렬로 서 있는 빌딩을 정면에서 바라볼 경우 i번째 빌딩은 (i, 0)과 (i, Hi)를 잇는 두께가 0인 선분으로 생각할 수 있다. 이때 임의의 i번째 빌딩과 j번째 빌딩에 대해서, i번째 빌딩의 옥상을 나타내는 점 (i, Hi)와 j번째 빌딩의 옥상을 나타내는 점 (j, Hj)를 잇는 선분이 다른 모든 빌딩과 만나지 않거나 빌딩의 끝점에서만 만날 경우 두 빌딩은..

https://www.acmicpc.net/problem/12792시간 제한메모리 제한1초256MB문제곧 다가올 학교 축제를 위해, 쿠사과는 참가비를 내고 여러 사람이 동시에 즐길 수 있는 게임을 만들었다. 이 게임의 알파이자 오메가는 추첨기이다. 이 추첨기는 1번부터 N번까지 둥글게 구멍이 위 아래로 하나씩 나 있고, 추첨기 윗편 구멍에 구슬을 넣으면 안에서 정해진 통로에 따라 복잡하게 움직이다가 아래 구멍 중 하나로 떨어지게 된다. 게임은 간단하다. N명이 동시에 모여 추첨기에서 1부터 N이 적힌 자리에 각각 한 명씩 선 뒤, 쿠사과가 1번 사람부터 N번 사람까지 차례로 돌아가면서 구슬을 하나씩 넣고, 어느 위치에 떨어지는지 본다. 만약 어떤 사람이 자신의 위치에서 넣은 구슬이 그대로 자신이 선 위치..

https://www.acmicpc.net/problem/14601시간 제한메모리 제한1초512MB문제오늘은 민규가 훈련소에 입소하는 날이다. 모든 행사를 마치고 생활관으로 돌아와서 쉬려는데 갑자기 교관이 들어오더니 민규의 이름을 부르는 것이 아닌가. 당황한 채로 따라갔더니 이번엔 김준서를 아느냐고 물어보았다. 그 녀석이 샤워실 바닥을 깔았는데, 배수구 위치까지 막아버렸다면서 같은 학교 출신인 민규가 다시 깔라는 것이었다. 어떻게 타일을 깔지 고민하던 민규는 샤워실의 구조가 정사각형이면서 한 변의 길이가 2의 제곱수라는 사실을 알아냈다. 준서는 여기까지만 고려해서 2x2 크기의 타일로 바닥을 전부 채운 것 같은데, 문제는 이렇게 하면 배수구가 있어야 할 위치를 비울 수가 없다는 것이다. 이런저런 방법을 ..

https://www.acmicpc.net/problem/32251시간 제한메모리 제한2초(추가 시간 없음)1024MB(추가 메모리 없음)문제목이 마른 나무에게 물을 주자! 나무는 N개의 정점과 (N-1)개의 간선으로 이루어져 있으며, 어느 두 정점 간에도 단순 경로가 유일하게 존재하는 그래프를 의미한다. 1번 정점을 나무의 뿌리라고 부르자. 또 i번 정점과 직접 연결되어 있으면서 뿌리와의 단순 경로의 길이가 i번 정점보다 더 큰 정점을 i번 정점의 자식 정점이라고 부르자. 각 정점에는 열매가 하나씩 있다. 열매에 물을 주면 자신의 크기만큼 물을 흡수할 수 있고, 물을 주면 가능한 최대로 흡수한다. 또한 흡수한 물의 양만큼 열매의 크기가 커진다. 자식 정점이 하나 이상 있다면, 열매가 흡수하고 남은 물은..

https://www.acmicpc.net/problem/25793시간 제한메모리 제한1초1024MB문제코코는 특이하게 생긴 화이트 초콜릿과 다크 초콜릿을 무한히 많이 갖고 있다. 화이트 초콜릿은 각 모서리의 길이가 1인 사각 피라미드이고, 다크 초콜릿은 각 모서리의 길이가 1인 정사면체 모양이다. 어느 날 코코는 이 초콜릿들을 가지고 놀다가, 초콜릿을 잘 쌓으면 더 큰 사각 피라미드를 만들 수 있다는 사실을 알아냈다. 바닥면의 직사각형의 크기가 R×C인 피라미드를 쌓는 구체적인 방법은 다음과 같다.먼저 바닥을 R×C개의 화이트 초콜릿으로 채운다.화이트 초콜릿 사이사이를 다크 초콜릿으로 채운다.다크 초콜릿 사이의 공간을 다시 화이트 초콜릿으로채운다. 여기까지 진행하면 위쪽 면은 (R - 1)×(C - 1..

https://www.acmicpc.net/problem/12902시간 제한메모리 제한2초512MB문제Alice와 Bob은 두 명이 할 수 있는 게임을 하나 만들었다. 규칙은 다음과 같다.n개의 서로 다른 자연수로 이루어진 집합을 하나 갖고 시작한다.두 명은 번갈아서 차례를 가지며, 각자의 차례에 다음과 같은 동작을 수행한다: 집합 내에서 서로 다른 두 자연수 x와 y를 고른다. 단, |x-y|가 집합 내에 존재해서는 안 된다. 이렇게 x와 y를 고른 이후, 그것을 고른 사람이 |x-y|를 집합 내에 넣는 것으로 그 사람의 차례가 종료된다.더 이상 고를 수 있는 (x,y)가 없는 사람이 패배한다.두 사람이 모두 최적의 전략으로 플레이할 때, 처음에 주어진 n개의 자연수에 대해 누가 승리하게 될지 출력하시..

https://www.acmicpc.net/problem/15311시간 제한메모리 제한1초512MB문제약장수 강욱이는 오늘도 약을 판다. 짬에서 나오는 Vibe로 화려한 언변을 구사하는 강욱이는 최고의 약장수이다. 하지만 이런 그에게도 고민거리가 하나 있으니... 동규라는 단골 손님이 있는데, 그는 매일 약을 1알에서 100만알 사이의 랜덤한 자연수 개수만큼 원했다. 주문을 받은 강욱이는 약 상자에서 한 알씩 약을 세서 꺼내주곤 했는데, 그것이 답답했던 동규는 강욱이에게 매번 화를 냈던 것이다. 이러다 동규가 자기를 때리지 않을까 무서웠던 강욱이는 동규가 원하는 만큼의 약을 빨리 건네주기 위한 방법을 고민하기 시작했다. 그는 곧 소싯적에 공부했던 Algorithm을 이용해 다음과 같은 방법을 생각해 냈다..