groti's blog

1. 문제 해석 https://www.acmicpc.net/problem/18235 18235번: 지금 만나러 갑니다 첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B) www.acmicpc.net 오리는 점 A 육리는 점 B에 위치하고 이다. 1일 차에는 1만큼 점프하고 하루가 지날 때마다 2배씩 멀리 점프한다. 현재 위치가 X이고 서로를 시작한 지 Y일 지났다면 X + 2^(Y-1) 또는 X - 2^(Y-1)로 점프한다. 0 이하 또는 N + 1 이상의 지점으로 점프할 수 없다. 오리와 육리가 만날 수 있는 최소 일수를 구해야 한다. 2. 접근방법 오리와 육리가 만나는 최소 일수를 구하는 것 이기 때문에 각각의 점프 위치를 BFS 탐..

1. 문제 해석 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 줄에 당근 i의 wi와 pi가 공백으로 구분되어 주어진다. (1 ≤ i ≤ N, 1 ≤ wi ≤ pi ≤ 100, wi와 pi는 정수) www.acmicpc.net 텃밭에 N개의 당근을 심을 수 있다.(1 > p; vec.push_back({ p, w }); } sort(vec.begin(), vec.end()); long long ans = 0; for (int..

1. 문제 해석 https://www.acmicpc.net/problem/18116 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 부품인지 알 수 있다. 그래서 성규는 호재의 지시에 따라 부품들을 정리하기로 하였다. 부품들은 1부터 106까지의 정수로 표현된다. 그리고 부품 i가 속한 로봇은 robot(i)라고도 표현한다. 예를 들어, 부품 11과 부품 22가 로봇 A의 부품이라고 알고 있는 경우, www.acmicpc.net 1부터 10^6까지 정수로 표현된 로봇의 부품이 있다. 부품 i가 속한 로봇은 robot(i)라고 표현한다. 서로 ..

1. 문제 해석 https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기 www.acmicpc.net 카드를 놓는 방법이 3가지 있다. N개의 카드를 다 놓은 후의 결과는 항상 내림 차순이다. N개의 카드 놓는 방법이..