하바나바나나

https://www.acmicpc.net/problem/15224 15224번: EvenOdd Consider the following function f(X), which takes a single positive integer as argument, and returns an integer. function f(X): iterations := 0 while X is not 1: if X is even: divide X by 2 else: add 1 to X add 1 to iterations return iterations It can be s www.acmicpc.net 어떤 정수 $x$에 특정한 연산을 반복해서 취할 때, $x$가 1일 될 때까지 취해야 하는 연산의 갯수를 $f(x)$라고 정의해..

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 단방향 그래프가 주어지고 $M$개의 $u, v$가 주어질 때, 몇 개의 단방향 길을 양방향 길로 바꿔야 $u$에서 $v$로 갈 수 있는지 출력하는 문제입니다. 플로이드-워셜을 응용하면 해결할 수 있습니다. 단방향 간선의 경우 해당 방향으로 이동할 때는 바꿔야 하는 길이 없으므로 코스트가 0이라고 할 수 있습니다. 단방향 간선의 반대 방향의 경우 해당 방향으로 이동하려면 길을 하나 바꿔야 함으로 ..

https://www.acmicpc.net/problem/9567 9567번: Empty Stalls Farmer John's new barn consists of a huge circle of N stalls (2

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 어떠한 수보다 보다 등장 횟수가 많으면서 오른쪽에 등장하는 수를 구하는 문제입니다. 오른쪽에 등장하는 수라는 점에서 감을 잡을 수도 있는데, stack을 사용하여 등장 횟수의 내림차순으로 인덱스들을 관리해주면 됩니다. 스택의 위에 있는 인덱스보다 등장 횟수가 많은 수를 현재 보고 있을 경우, 현재 보고 있는 수가 해당 인덱스의 오등큰수가 됩니다. 이를 배열을 돌면서 실행해주면 각 수의 오큰수를 구할 수 있습니..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 딱 보면 위상정렬로 착각하기 쉬운 문제입니다. 위상정렬보다는 훨씬 쉬운 방법으로 풀립니다. 위상정렬을 하듯이 생각해보면, 어떠한 사건 $a$가 사건 $b$보다 먼저 일어났다는 것은, $a$에서 $b$로 가는 단방향 간선이 존재한다고도 생각할 수 있습니다. 모순되는 사건이 존재하지 않는다고 했으므로, 그렇게 구성된 그래프는 항상 DAG의 형태를 띄게 됩니다. 그래프를 구성한 후 해당 그래프에..

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 여러 알파벳으로 이루어진 2차원 격자가 주어졌을 때, 해당 격자에서 같은 알파벳으로 이루어진 길이 4 이상의 사이클이 존재하는지 판단하는 문제입니다. dfs로 cycle을 찾듯이 풀면 되는데, 한 번 방문한 점은 시작 지점이 아닌 이상 다시 방문하지 않도록 해야 합니다. 이를 구현하기 위해 시작 위치와 현재 위치, 그리고 몇 개의 점을 지났는지 기록하고 4개 이상의 점을 지났고 시작 위치..

https://www.acmicpc.net/problem/4913 4913번: 페르마의 크리스마스 정리 각 테스트 케이스에 대해서, 한 줄에 L U x y를 출력한다. 여기서 L과 U는 입력으로 주어진 값이고, x는 구간 [L,U]에 포함된 소수의 개수, y는 [L,U]에 포함된 소수중 제곱수의 합으로 나타낼 수 있는 www.acmicpc.net 풀이 자체는 어렵지 않은 문제입니다. 음수는 소수가 아니므로, 1부터 1000000 사이의 모든 소수를 에라체를 이용해 미리 구해준 뒤 누적합을 이용해 매 쿼리마다 소수의 개수와 제곱수의 합으로 표현되는 소수의 개수를 구해주면 됩니다. 단, 주의해야 할 점은 2 역시 제곱수의 합으로 표현되는 소수라는 점입니다. (1 + 1 = 2) 이걸 몰라서 세 번 틀렸습니다..

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 스택을 사용하여 풀 수 있는 문제입니다. 문자열의 P를 PPAP로 바꿀 수 있다는 말은, 달리 말하면 PPAP을 P로 바꾸어 원래 문자열을 복원할 수 있다는 뜻입니다. 문자열을 쭉 확인하며 스택에 문자들을 넣어준 뒤, 맨 마지막 네 문자가 PPAP라면 P로 바꾸는 과정을 반복하여 마지막에 스택에 P만 남아있다면 PPAP를, 아니라면 NP를 출력하면 됩니다. 아래는 코드입니다. #include #define FastIO ios::sync_with_s..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 원래는 14639번을 풀려고 했는데... 아무리 생각해도 못 풀고 힌트를 들어도 못 푸니까 cologne 님이 던져준 문제입니다. 연속된 전구가 주어지고 $i$번째 전구는 $i-1$, $i$, 그리고 $i+1$번째 전구를 toggle 할 수 있습니다. 원래의 전구 상태와 바꾸고자 하는 전구 상태가 주어질 때, 최소 toggle 횟수를 찾아야 합니다. 이는 그리디한 방법..

https://www.acmicpc.net/problem/4181 4181번: Convex Hull 때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소 www.acmicpc.net 말 그대로 컨벡스 헐을 구하는 문제입니다. 컨벡스 헐을 구할 수 있으면 그냥 구할 수 있습니다. 컨벡스 헐을 구할줄 몰라도 문제에서 어떤 점이 볼록 껍질에 포함되는지 알려주기 때문에 각도정렬을 슥삭슥삭 하면 구할 수 있습니다. 편의를 위해 반시계 방향의 시작점(x값이 가장 작은 점, 같다면 y값이 가장 작은 점)을 기준으로 기울기를 구해줍니다. 이렇게 하면 다른 모든 점들은 ..