돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/17613 문제 풀이 일단 문제를 한 번 보자. "만일 점프간격을 2배씩 계속 증가시켜 마지막 점프에서 목표 수 x를 지나칠 것 같으면, 필요한 경우 언제든지 점프 간격을 다시 처음 상태인 간격 1로 되돌아 갈 수 있다. 이것을 재시작이라고 부른다." 라는 문구가 굉장히 중요한 부분이다. 굳이 이 문구를 통해서 유추를 할 필요는 없지만, 풀이를 생각하는 과정에서 이 문장은 풀이의 일부에 확신을 주게 된다. Phase 1 현재 개구리가 $2^i$ 까지 한 번에 뛰었다. 그리고 $2^{i+1}$을 뛸 수 있는 상황이다. 그런데 안 뛸 이유가 있을까? $2^{i+1}$은 1부터 $2^i$까지의 합보다 크다. 1번의 점프로 i번의 점프의 효..

문제 링크 : https://www.acmicpc.net/problem/17612 문제 풀이 딱히 사고의 흐름이라고 할 게 없다. 상황의 형태와 여러가지 조건들을 주어지고 이를 시뮬레이팅 할 수 있는 코드를 짜는 구현 문제이기 때문이다. 고객들이 어떤 순서로 나갈지를 알아내야 한다. 고객들은 번호 순으로 입장하고, 빈 구역이 있으면 바로 입장하며, 각 고객별로 주어진 시간만큼 있다가 퇴장한다. 이때 입장할 구역이 여러군데면 가장 작은 번호로 가며, 나갈 때는 동시에 끝나면 번호가 큰 순서대로 나간다. 정리하면 나가는 순서는 일련의 규칙을 따른다. 일련의 규칙에 따른 정렬 -> 우선순위 큐. 솔직히 따지고 보면 우선순위 큐 연습문제라고 봐도 무방하다. 동시에 자리가 나면 무조건 작은 번호의 구역으로 이동하..

문제 링크 : https://www.acmicpc.net/problem/1028 문제 풀이 다이아몬드는 4개의 선분으로 이루어진다. 정확히 맞물리는 4개의 길이가 같은 대각선을 찾으면 된다. 어떤 위치로 부터 k개의 연속된 1이 대각선 방향으로 있으면 k 이하의 임의의 길이의 대각선을 찾을 수 있다는 것이다. 따라서 우리는 모든 위치에 대해서 4개의 방향으로 각각 어디까지 1이 이어져 있는지를 알고 있어야 한다. 따라서 다음과 같이 DP 값을 정의할 수 있다. ld[i] = 왼쪽 아래로 이어져 있는 1의 개수, rd[i] = 오른쪽 아래로 이어져 있는 1의 개수, lu[i] = 왼쪽 위로 이어져 있는 1의 개수, ru[i] = 오른쪽 위로 이어져 있는 1의 개수. 이는 주어진 맵을 스캔하는 과정에서 $O..

문제 링크 : https://www.acmicpc.net/problem/17834 문제 풀이 문제를 보자마자 홀짝성을 생각할 수 있다. 다시 말하자면 주어진 그래프를 2가지 색으로 칠할수 있는지를 물어보는 문제이다. 만약 주어진 그래프를 2가지 색으로 칠할 수 있다면, 두 동물의 시작 색깔이 다르면 영원히 잡을 수 없게 되기 때문이다. 주어진 그래프를 두 가지 색으로 칠할 수 있는지를 확인해 보자. 이는 dfs 한 번으로 쉽게 확인할 수 있다. dfs를 기본적으로 돌면서 두 가지 색을 번갈아가면서 칠해준다. dfs를 돌 다 보면 이미 방문한 정점을 거를때가 있는데, 거르기 전에 현재 정점과 다른 색으로 칠해져 있는지를 확인해주면 된다. 만약 같은 색이라면 두 가지 색으로 칠할 수 없는 그래프이다. 하지만..

문제 링크 : https://www.acmicpc.net/problem/2924 문제 풀이 주어진 수열의 i번째 값을 A[i]라고 하자. 우리는 $C\leq k\leq N-D$ 인 k들에 대해서 모든 A[A[A[A[A[...A[k].]]]]=k가 되는 최소 횟수를 찾아야 한다. 당연히 B번을 돌려보는 것은 문제를 해결할 수 있는 방법이 아니다. 최소 횟수를 m이라고 하면 답은 (B회까지 처음과 같은 형태의 개수 - A-1회 까지 처음과 같은 형태의 개수) 이기 때문에 (b+m-1)/m-(a+m-2)/m의 형태가 된다. 따라서 m을 구하기만 하면 된다. 각 k에 대해서 다시 k로 돌아오는데 까지 걸리는 횟수를 알게 되면 $C\leq k\leq N-D$ 인 k들에 대해서 그 횟수들을 모두 lcm 취해주면 모..

교내 경시를 대비하여 가볍게 돈 셋을 정리하는 글이다. Blackking26과 함께 7월 15일 19시 부터 20시 40분까지 100분 간 진행했다. 지난번 문제는 너무 쉽기도 하고, 구현 연습이 절실했기 때문에 문제는 골드 하위 랜덤 5문제와 실버 상위 구현 태그가 달린 5문제를 넣어서 10문제로 설정했다. 결과는 10문제 중에 7문제를 풀었다. 비 구현 4문제와 구현 3문제이다. A. 주기문으로 바꾸기 주기로 인해서 같은 글자가 되어야 하는 애들끼리 묶어서 생각하자. 당연히 가장 많은 글자를 따라 가는 것이 이득이다. 따라서 주기의 같은 위치에 있는 글자끼리 묶어서 가장 많은 수의 글자가 아닌 글자가 몇 개인지 세기만 해서 더하면 끝이다. B. 파이프 옮기기 1 아무리 봐도 딱봐도 DP. 어떤 칸에 ..

문제 링크 : https://www.acmicpc.net/problem/15907 문제 설명 n개의 수들 중에서 최대한 많은 수를 포함하는 ax+b (a는 2이상의 정수, b,x 는 정수) 꼴을 찾아내야 한다. 이때 그 꼴으로 표현할 수 있는 수의 갯수를 출력하면 된다. 문제 풀이 ax+b 꼴에 최대한 많은 수를 포함시켜야 한다. 생각을 해보자. 2로 나눈 나머지로 수들을 분리하는것이 무조건 4,6,8,10..등으로 수를 분리하는 것보다 이득이다. 이는 3,4,5... 등에 대해서도 모두 적용되는 논리이다. i로 분리해서 확인하면 ki꼴의 수에 대해서는 확인하지 않는 것이 이득이다. 이러면 무엇이 떠오르는가? 당연히 소수이다. 즉, 소수에 대해서만 판별을 하면 된다는 것이다. 2000000만까지의 모든 ..

문제 링크 : https://www.acmicpc.net/problem/15311 문제 풀이 친구가 재밌는 문제라고 풀어보라고 했던 문제가 백준에, 심지어는 나는코더다 2017 송년대회에 있을줄은 몰랐다. 아이디어성 문제이다. 루트, 버킷에 익숙한 사람은 좀 더 쉽게 보일 수도 있다. 사실 풀이를 어떻게 써야할지 모르겠다. 그래도 최대한 사고의 흐름을 써보려고 한다. 맨 처음에는 이진법을 생각했다. 모든 값을 다 표기하는데 이진법만큼 쉽고 간단한 방법이 떠오르지 않았다. 하지만 이진법은 자릿수가 계속 올라간다는 문제가 있었다. 1 2 1 4 2 1 뭐 이런식으로 할 수도 없었고, 자릿수가 많은 표기법은 좋지 못하다는 생각을 했다. 2000과 1000000을 계속 생각해봤다. $n^k=1000000$이고 ..

문제 링크 : https://www.acmicpc.net/problem/1395 문제 태그 더보기 Segment Tree Lazy Propagation 문제 풀이 문제를 보자. 거의 Segment Tree Lazy Propagation 연습문제라고 해도 될 정도로 기본적인 연산을 요구하고 있다. 구간의 값을 바꾸는 연산과 구간의 값을 구하는 연산. 값을 바꾸는 연산은 구간 내의 1을 모두 0으로 바꾸고 0을 모두 1로 바꾸는 연산이다. 이때 기존의 s~e 구간을 담당하고 있는 구간의 값이 val이라면 연산을 한 후 새로운 값은 e-s+1-val 로 쉽게 구할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

문제 링크 : https://www.acmicpc.net/problem/17167 문제 설명 두 숫자 a,b 가 주어져 있을 때, 5000번 이하의 a+=b, a+=a, b+=b, b+=a의 4가지 행동을 통해서 a와 b를 똑같게 만들 것이다. 이때 걸리는 횟수와 그 방법을 출력하시오. 문제 풀이 일단 범위를 줄이는 데 집중을 해보자. 3,9로 수를 시작하는 것과, 1,3으로 수를 시작하는 것은 다른 결과가 나올까? 라는 질문으로 시작을 하게 되면 아니라는 결론이 나오게 된다. 좀 더 확장시켜서 생각을 해보면 항상 a,b를 같게 만드는 일련의 행동들은 c=gcd(a,b)인 c에 대해서 a/c, b/c를 같게 만들 수 있다. 물론 반대도 성립한다. a+=a는 a를 두 배 시키는 것과 동치이다. 따라서 b가..