https://www.acmicpc.net/problem/2207시간 제한메모리 제한2초128MB문제국제 가위바위보 협회의 회원인 얼드학원의 원장선생님은 가위바위보를 매우 좋아한다. 종종 학생들이 학원에서 딴짓을 하다 걸렸을 경우, 가위바위보 게임을 해서 처벌 여부를 결정하고는 한다. 어느 날 학원에서 N(1 ≤ N ≤ 10,000)명의 학생들이 딴짓을 하다 걸리게 되었다. 걸린 학생의 수가 너무 많아서, 원장선생님은 새로운 방법을 제안했다. 원장선생님이 총 M(1 ≤ M ≤ 10,000)번 가위바위보를 혼자서 하고, 이때 학생들이 원장선생님이 몇 번째에 무엇을 낼지를 알아맞히면 살려주기로 한 것이다. 그런데 찍기에 소질이 있는 얼드학원의 학생들은 모두 원장선생님의 패턴을 파악하여 살게 되었다. 그래서 ..

https://www.acmicpc.net/problem/18867시간 제한메모리 제한0.1초 (추가 시간 없음)1024MB문제욱제는 2020년 04월 02일 목요일 14시 00분에 논산 육군훈련소에 입소했다. 욱제는 2020년 04월 29일 수요일에 사회로 돌아온다. 욱제에게 격려의 메세지를 남겨주자. 단, 편지의 내용은 아래의 조건을 만족해야 한다. 답안은 [A-Za-z0-9 ] ASCII 문자로 구성하는 것을 권장하며, 이를 이용해 문제를 해결할 수 있음이 보장된다. 단, 문제의 체커(#)를 보고 이해한다면, 한글, 이모지 등 어떤 문자를 제출해도 상관이 없다.1. 답안의 크기는 990316byte 이하여야 한다. 2. 채점기는 답안을 1byte 단위로 끊어서 읽는다. 3. i번째 byte를 int..

https://www.acmicpc.net/problem/18137 시간 제한메모리 제한0.5초256MB문제 입력오른쪽과 위쪽으로 무한히 많이 뻗어 나가는 격자판이 있다. 이 격자에서 왼쪽에서 x번째, 아래에서 y번째 칸에는 수가 쓰여 있다. 이 방법을 사용하면, 각 칸을 하나의 양의 정수에 일대일 대응시킬 수 있다. 여기서 나이트(체스의 기물 중 하나)는 격자판을 이동하려고 한다. 나이트는 두 칸 전진 후, 전진한 방향에서 오른쪽 혹은 왼쪽 중 한 방향으로 한 칸을 이동한다. 전진하는 방향은 위쪽, 아래쪽, 오른쪽 혹은 왼쪽 중 아무 방향이어도 상관없다. 하지만 격자판을 나가서는 안 된다. 즉, 나이트가 격자판 바깥으로 나가는 경우가 없다고 할 때 8칸 중 하나로 이동할 수 있다. 하지만 가장 왼쪽 아..

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번 정점의 자식 정점이라고 부르자. 각 정점에는 열매가 하나씩 있다. 열매에 물을 주면 자신의 크기만큼 물을 흡수할 수 있고, 물을 주면 가능한 최대로 흡수한다. 또한 흡수한 물의 양만큼 열매의 크기가 커진다. 자식 정점이 하나 이상 있다면, 열매가 흡수하고 남은 물은..