본문 바로가기
반응형

전체 글282

백준 12169번 Infinite House of Pancakes - C++(cpp) 풀이 1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다. 2. 총 i번의 노말 턴을 진행하는 경우, 스페셜 턴을 전부 진행한 뒤 다이너들의 접시에는 전부 i개 이하의 팬케이크가 남아있어야 한다. 3. 총 i(1 ≤ i ≤ 1000) 번의 노말 턴을 진행하는 모든 경우를 고려하여 최솟값을 찾는다. 1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다. 노말 턴과 스페셜 턴을 한 번씩 진행해야 한다고 하자. 노말 턴 → 스페셜 턴의 순서로 진행할 때보다, 스페셜 턴 → 노말 턴의 순서로 진행할 때 같거나 더 적은 시간이 든다. 현재 다이너가 d명 있다.. 2022. 3. 25.
백준 14791번 Tidy Numbers - C++(cpp) 풀이 1. 10^18 이하의 tidy number를 모두 구한다. 2. tidy number들을 정렬한 뒤, N의 upper bound를 구한다. 3. tidy_numbers[upper_bound-1]이 N 이하인 가장 큰 tidy number이다. 1. 10^18 이하의 tidy number를 모두 구한다. 10^18 이하의 tidy numbers는 총 4,686,824개이다. 생각보다 많지 않으므로 이것을 모두 구해주자. tidy number를 문자열로 생각하면, 모든 부분 문자열 또한 tidy number이다. 따라서 길이가 len인 tidy number X에, X의 마지막 문자보다 크거나 같은 문자를 덧붙이면 길이가 len+1인 tidy number를 만들 수 있다. 이러한 사실을 사용해서 재귀를 통해.. 2022. 3. 23.
백준 14789번 Oversized Pancake Flipper - C++(cpp) 풀이 1. 한 자리에서 두 번 이상 뒤집을 필요가 없다. 2. 첫 팬케이크를 뒤집을 수 있는 방법은 가장 왼쪽의 K개를 뒤집는 것뿐이다. 3. 왼쪽부터 차례로 happy side가 되도록 뒤집는다. 1. 한 자리에서 두 번 이상 뒤집을 필요가 없다. 한 자리에서 두 번 이상 뒤집을 필요가 없다. 짝수번 뒤집는 것은 안 뒤집는 것과 같고, 홀수번 뒤집는 것은 한 번 뒤집는 것과 같기 때문이다. 따라서 각 자리에서 뒤집을지 말지만 결정하면 된다. 2. 첫 팬케이크를 뒤집을 수 있는 방법은 가장 왼쪽의 K개를 뒤집는 것뿐이다. 뒤집을 수 있는 자리는 총 N-K+1개이다. 이때 첫 번째 팬케이크를 뒤집을 수 있는 자리는 가장 왼쪽의 K개를 뒤집는 자리뿐이다. 3. 왼쪽부터 차례로 happy side가 되도록 뒤집는다.. 2022. 3. 23.
백준 12181번 Googlander - C++(cpp) 풀이 + 그림 설명 1. i행에서 오른쪽으로 꺾으면 더 이상 i행 위는 방문할 수 없다. 2. 따라서 R-i행에서 오른쪽으로 꺾으면 i개 행, C-1개의 열이 있는 격자판에서 출발하는 상황과 같아진다. 3. 시작점에서 쭉 직진하다가 0~(R-1) 행에서 오른쪽으로 꺾는 모든 경우의 수를 더한다. 1. i행에서 오른쪽으로 꺾으면 더 이상 i행 위는 방문할 수 없다. 오른쪽으로만 회전할 수 있기 때문에, 북쪽을 향하고 있는 상황에서 오른쪽으로 꺾으면 해당 지점보다 위에 있는 칸은 더 이상 방문할 수가 없다. 2. 따라서 R-i행에서 오른쪽으로 꺾으면 i개 행, C-1개의 열이 있는 격자판에서 출발하는 상황과 같아진다. 따라서 시작점에서부터 쭉 직진하다가 R-i행에서 오른쪽으로 꺾으면 (i, C-1)인 격자판에서 출발하는 상황과.. 2022. 3. 22.
백준 12177번 Dreary Design - C++(cpp) 풀이 1. G-R과 B-G를 고정한다. 2. R, G, B 값이 모두 0 이상 K이하가 되도록 하는 R 값을 모두 구한다. 3. 가능한 모든 (G-R, B-G) 쌍에 대해 1,2를 반복한다. 1. G-R과 B-G를 고정한다. K 범위가 굉장히 크기 때문에 K 대신 V를 기준으로 생각해준다. 결국 R, G, B 값의 차를 모두 V 이하로 만들어야 한다. G-R 값과 B-G 값을 정하고 나면, R값만 정해도 G, B 값이 저절로 정해진다. 2. R, G, B 값이 모두 0 이상 K이하가 되도록 하는 R 값을 모두 구한다. 1에서 고정한 값을 G-R = i, B-G = j 라고 하자. 이를 가지고 G와 B를 나타내면, G = R+i, B = R+i+j 이다. R, G, B 값이 모두 0 이상 K 이하여야 하므로, .. 2022. 3. 22.
반응형

티스토리툴바