https://www.acmicpc.net/problem/5681시간 제한메모리 제한1초128MB문제KDK방송국은 새로운 게임 쇼를 하나 만들었다. 참가자는 선택을 몇 개 하게 되고, 이 선택에 따라서 상품을 얻게 된다. 먼저, 공이 삼각형 모양으로 쌓여져 있고, 각 공에는 정수 값이 하나씩 쓰여 있다. 아래 그림은 한 예이다.참가자는 공을 고를 수 있고, 고른 공에 쓰여 있는 숫자의 합이 점수가 된다. 공을 고르면, 그 공은 삼각형에서 제거된다. 점수가 높을수록 좋은 상품을 받게 된다. 하지만, 참가자는 그 공의 위에 있는 공을 고른 경우에만 그 공을 고를 수 있다. 또, 참가자는 공을 고를 것인지, 게임을 중단할 것인지 선택할 수 있다. 만약, 공을 하나도 고르지 않은 경우에 점수는 0이 된다. 프로..

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)를 잇는 선분이 다른 모든 빌딩과 만나지 않거나 빌딩의 끝점에서만 만날 경우 두 빌딩은..