https://www.acmicpc.net/problem/18858시간 제한메모리 제한1초1024MB문제훈련소로 가는 날 욱제는 문득 떠올렸다. 훈련소가 논산에 있는 이유는 무엇일까? 왜 why? 그것은 바로…            논산(non-산)은 산이 아니기 때문이다. 길이가 3인 수열 a1, a2, a3가 산임은 a1  a3임을 의미한다. 어떤 수열이 논산임은 수열의 인접한 세 항이 산인 경우가 없음을 의미한다. 다시 말해, 길이 N의 수열 a에 대해 2 ≤ i  ai+1인 경우가 없다. 논산인 수열이 몇 개가 있는지 알아보자.입력첫째 줄에 N과 M이 주어진다.1 ≤ N ≤ 1,0001 ≤ M ≤ 100 출력1 이상 M 이하의 정수로 이루어진 길이 N의 수열 중 논산인 것의 개수를 998,244,3..

https://www.acmicpc.net/problem/11781 시간 제한메모리 제한1초256MB문제엔지니어의 행복도는 퇴근 후 집에 도착하는 시각이 늦을수록 낮아진다는 것이 증명되었다.조이의 대표 레드는 엔지니어의 행복도를 최대한 높여야 할 의무가 있기 때문에, 신중하게 퇴근 시간을 조정하기로 하였다.하지만 퇴근 시간을 조정하려면 먼저 엔지니어들이 집에 도착하는 시간을 알아야만 했다.이 문제를 미카에게 맡기려고 했지만, 6시가 넘어 미카는 이미 퇴근해버렸기 때문에 레드는 고민에 빠지고 말았다.레드를 도와 레드와 조이 엔지니어 모두의 행복도를 높여보도록 하자!회사가 있는 서울은 N개의 지점으로 되어있다.각 지점은 1번부터 N번의 번호를 가지고 있고, 회사는 1번 지점에 있다.M개의 도로들은 서로 다른..

어떤 그래프에서 정점을 제거했을 때, 그래프가 분리되어버리는 경우가 있습니다. 또는 간선을 제거 했을 때 분리되는 경우도 있습니다. 각각의 정점과 간선을 "단절점", "단절선"이라고 합니다. 1. 단절점의 특징단절점과 단절선이 갖는 중요한 특징이 있습니다. 하나의 연결그래프를 dfs로 탐색하면 탐색 경로가 트리의 형태로 남게 됩니다. 여기서 어떤 정점 n을 탐색했을 때 그 정점으로부터 탐색된 하위 정점들에서 n의 상위 정점으로 돌아가는 경로가 하나도 없다면 n은 단절점이 됩니다. 그러니까, n을 제거하면 그보다 하위에 있는 모든 정점들은 n보다 상위 정점에서 분리되어버립니다. 돌아가는 길이 없으니까요. 이거 뭔가 지난 번에 정리한 SCC와 비슷한 느낌인데, 단절점을 찾는 과정이 SCC의 일부이기 때문입니..

https://www.acmicpc.net/problem/31537시간 제한메모리 제한1초1024MB문제누구나 그렇듯 동우는 출근하기 싫다. 그래도 출근해야 한다. 동우가 다니는 회사는 신기한 회사이다. 총 N명의 직원이 있는데, 이 중 최대 1명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만  1명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다.동우는 회사의 업무가 정상적으로 진행되는 것이 신기해 현재 시각으로부터 최근 M시간 동안 N명의 직원 각각이 총 몇 시간씩 출근했는지 살펴보았다.직원들은 모두 정각에만 출근해 정각에만 퇴근하며, 한 사람이 여러 번 출근 혹은 퇴근할 수 있다. 최근 M시간 동안 업무를 계속 정상적으로 진행할 수 있도록 하는, N명의 직원이 출근한 조합의..

https://www.acmicpc.net/problem/14939시간 제한메모리 제한1초128MB문제전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라 입력10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다. 출력모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.풀이전구 하나를 조작하는 상황을 생각해봅시다. 전구와 인접한 4개의 전구까지 5개의 전구가 반전됩니다. 2번..

https://www.acmicpc.net/problem/32647시간 제한메모리 제한1초1024MB문제혁준이의 친한 친구 골드바흐흑흙은 호기심이 아주 많다.어느 날, 골드바흐흑흙이 혁준이에게 물었다. 중복되지 않는 A이상 B이하인 소수들의 합으로 K를 표현할 수 있는 경우의 수는 얼마나 될까?혁준이는 다섯 살이라서 골드바흐흑흙의 질문에 답할 수가 없으므로, 여러분이 대신 구해주자.고른 수들은 같고 순서만 다른 경우들은 하나의 경우로 처리한다. 예를 들어, {2, 3}과 {3, 2}는 같은 경우이다. 입력첫 번째 줄에 양의 정수 A, B, K가 공백을 사이에 두고 주어진다. (1 ≤ A  출력문제의 정답을 출력한다. 풀이A와 B의 제한 조건을 잘 보면 B - A가 300 이하라는 특이한 부분이 있습니다...

https://www.acmicpc.net/problem/23845시간 제한메모리 제한1초1024MB문제인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 Xi이다. 인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (Q - W + 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라. 하나의 마트료시카의 가격은 Q × T로 책정된다고 한다. 하령이는 가지고 있는 인형을 적절히 조합하여 마트료시카들을 구성해서 최대의 수익을 올리고 싶..

어떤 자연수 n이 소수인지 판별하는 좋은 방법이 여러 가지 있습니다. 우선 가장 근본인 2부터 n - 1까지의 수로 n을 나누어보는 방법이 있습니다. 약수가 1과 n 말고 또 있는지 확실히 알 수 있습니다. 그런데 n이 만약 1,000,000,007 같은 수라면, 혹은 2136279841-1처럼 답도 없이 큰 소수에 대해서는 실행 가능성이 좀 낮거나 아예 없습니다. 그리고 구현하기 쉽고 성능도 확실한 "에라토스테네스의 체"가 있습니다. 근데 이건 특정한 소수 하나를 판별하기 보다 N까지의 소수를 모두 구하는데 좋은 방법입니다. n까지의 모든 소수를 빠짐 없이 확실하게 구할 수 있는 결정론적인 성질이 있습니다. 하지만 역시 자릿수가 좀 커진다 싶으면 매우 느려지는 단점이 있습니다. 가장 최적화된 에라토스테..