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

1. 충족가능성 문제(Boolean satisfiability problem, SAT)여러 변수로 논리 값들이 주어졌을 때, 그 논리 값들로 이루어진 식이 참이 되는 논리 값의 상태가 존재하는가에 대한 문제입니다. 이거 약간 뭐랑 비슷하냐면 대학교 시간표 짜는 거랑 비슷합니다. 작년 연구부장 역임했던 바로 생각해보면 전담 시간표 짜는게 딱 이 SAT 문제 입니다. 제가 일반 종합대학을 다녀본 경험이 없으니 그냥 교육대학교에서 만났던 과목으로 생각해봅시다. (제가 다녔던 대학교는 사실 수강신청이랄 것도 없긴 했습니다. 그냥 예시 만들기 어려우니까 그런갑다 해봅시다.) 개설되는 다음 4개의 과목을 조건에 맞게 수강할 수 있는 방법이 있을까요?교육심리(A)와 교육철학(B) 중 한 과목은 반드시 수강해야 한다...

1. 강한 연결 요소강한 연결 요소는 그래프에 존재하는 서브 그래프입니다. 각각의 SCC는 하나의 사이클을 이룹니다. 그러므로 하나의 SCC내의 정점 u와 정점 v를 어떤 방법으로 선택해도 u에서 v로 이동하는 경로가 반드시 존재합니다. 그리고 각각의 SCC는 최대한 크게 구성되어야 합니다. 그러니까 하나의 그래프에 여러 SCC가 있을 때 서로 다른 SCC에 포함되는 두 정점간에는 단방향 경로가 존재할 수 있어도 사이클이 존재하는 경우가 하나도 없어야 합니다.이 그림의 유향그래프에서 여러 사이클을 찾아볼 수 있습니다. {a, d, b}와 {c, f}등이 있습니다. 하지만 이 중 SCC는 없습니다. {a, d, b} 사이클에서 d - b 사이에 e - f를 추가할 수 있습니다. {a, d, e, f, b}..

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번 사람까지 차례로 돌아가면서 구슬을 하나씩 넣고, 어느 위치에 떨어지는지 본다. 만약 어떤 사람이 자신의 위치에서 넣은 구슬이 그대로 자신이 선 위치..