돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/22883 의도된 풀이 주최측에서 의도한 풀이는 관찰을 통해서 주어진 임의의 게임판을 1*a 혹은 b*1 게임판으로 바꾸는 것이었다. 그렇게 되면 특정 게임판은 가로로만 이동이 가능하거나, 세로로만 이동이 가능하기 때문에 바로 둘이 각각 최대 몇턴 동안 살아남을 수 있는지가 구해진다. 따라서 직관적으로 누가 이길지를 계산할 수 있다. Stonejjun의 풀이 Part 1. 기본 지식과 유리도의 이해. 이 게임은 기본 상태보다 자신이 플레이 한 후의 상태가 자신에게 더 불리해지는 게임이다. 즉, 자신이 선공으로 이기면 후공으로 해도 이기며, 후공으로 지면 선공으로 해도 지고, 자신이 3번 행동을 하고 시작하면 훨씬 불리한 상태로 시작하..

문제 링크 : https://www.acmicpc.net/problem/13310 문제 태그 더보기 삼분 탐색, 로테이팅 켈리퍼스, 볼록 껍질 문제 풀이 가장 멀리 떨어진 두 별의 거리가 최소인 날을 구해야 한다. 다시 생각하면 임의의 두 별에 대해서 거리를 구한 후, 그 중 최댓값이 그 날에 대한 수치가 되는 것이다. 문제에서는 각 날별로 두 별의 거리를 구하는 것이지만 일단 관점을 바꿔서 두 별의 거리를 각 날별로 관찰해보자. V자. 이런식으로 나올것이다. 즉, 일정 시점까지는 두 별이 계속 가까워 졌다가, 일정 시점 이후부터는 계속 멀어질 것이다. 혹은 시간 구간 내에서는 계속 감소하거나 계속 증가할 수도 있다. 두 별에 대한 모든 거리 그래프를 겹친 후에 그 중 최댓값을 뽑아낸 그래프 G'를 생각..

BOJ 13302 고등부 1번 리조트 문제 링크 : https://www.acmicpc.net/problem/13302 문제 태그 더보기 DP 문제 풀이 각 주어진 상황에서 여러가지 조건 중 하나를 선택할 수 있으며, 선택을 통해서 최적의 결과를 얻어내야 하는 문제. -> 아무리 봐도 DP. 각 상태는 DP table에 저장하고, 선택할 수 있는 조건들은 DP 관계식으로써 표현할 수 있다. dp[i][j]를 i번째날 쿠폰을 j개 들고 있을 때, 사용한 돈의 최솟값 이라고 설정하면, 1일권을 산 경우, 3일권을 산 경우, 5일 권을 산 경우, 쿠폰을 쓴 경우에 대해서 각각 일수와 쿠폰 수의 변화를 생각하여 DP식 들을 여러개 만들어 주면 된다. 자세한 것은 아래의 코드를 참고하자. 평가 : 난이도는 확실히..

문제 링크 : 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/14870 문제 태그 DP, Two pointer, Segment Tree 문제 풀이 일단 기존 상태의 상황을 구하는 것은 매우 쉬울 것이다. 당연히 DP로 구할 수 있고, 이때의 식은 다음과 같다. $DP[i][j]=max(DP[i-1][j],DP[i][j-1])+arr[i][j]$ 여기서 특정위치의 arr값을 1을 올리거나 내리는 값을 했을 때 DP 테이블이 어떤식으로 바뀌는지 구해야 하는 문제이다. 만약 $DP[i-1][j]$와 $DP[i][j-1]$이 둘 다 바뀌었으면 $DP[i][j]$도 바뀌었을 것이다. 혹은 둘 중에 더 큰 값, 즉 영향을 받는 값이 바뀌면 바뀔 것이다. 여기서 한가지 관찰을 해야한다. 한 가로줄에 대해서..

문제 링크 : https://www.acmicpc.net/problem/14869 문제 태그 DP, deque, Segment Tree 문제 풀이 (의식의 흐름) 기본적으로 난이도가 있는문제이다. 일단 이 문제를 보자마자 이 문제가 DP라는 사실을 깨닫지 못했다면, 앞으로의 관찰은 거의 불가능한 난이도라고 생각해도 좋다. 그럼 DP 테이블을 정의해보려고 해보자. 일단 몇번째 강좌인지가 중요할 것이고, 어느 학원에서 듣는지가 중요할 것이다. 그렇게 $DP[i][j]$를 i번째 강좌를 j번 학원에서 수강할 때, 이때까지의 비용의 최솟값이라고 설정하자. 이러면 문제는 문제의 조건인, 한 학원에서 s~e 개를 연속해서 듣기를 만족할 수 없다. 그렇다고 $DP[i][j][k]$를 설정해서 k를 j번째 학원에서 현..

BOJ 14867 고등부 1번 물통 문제 링크 : https://www.acmicpc.net/problem/14867 문제 태그 bfs 문제 풀이 우리는 문제를 풀 때 항상 '상태'라는 것에 집중을 해야한다. 이번 문제에서는 문제의 디스크립션에서부터 이에 대한 언급을 해준다. 어떤 상태에서는 문제에서 주어진 행동을 할 수 있으며, 따라서 갈 수 있는 다음상태가 정해져 있다. 여기서 좀 생각을 해보면, 이를 그래프로써 표현하여 bfs로 문제를 해결할 수 있다. 각 상태가 그래프의 정점이 되며, 갈 수 있는 다음 상태(노드)들을 방향 간선으로 연결함으로써 그래프 문제로 옮길 수 있다. 이 과정에서 만약 (i,j) 를 1번 물통에 찬 물의 양이 i, 2번 물통에 찬 물의 양이 j로 생각해서 푼다면 한 가지 걸..

BOJ 8983 고등부 1번 사냥꾼 문제 링크 : https://www.acmicpc.net/problem/8983 문제 태그 스위핑 문제 풀이 N개의 x축에 붙은 지점중 임의의 어떤 지점에 대해서 택시거리가 L이하만큼 떨어져 있는지 판별하는 문제. 당연히 하나를 관찰하면 지점은 다 x축에 있으므로 모든 지점에 대해서 떨어진 y거리는 고정이다. 가장 중요한 관찰을 하자면 어떤 점에 대해서 가장 x값이 비슷한 지점과 거리가 가장 짧을 것이고 그 지점과 거리가 L보다 크면 당연히 나머지 지점에 대해서도 거리가 L보다 클 것이다. 따라서 그냥 가장 비슷한 x값을 찾는 문제. 배열에서 가장 비슷한 값을 찾는 것은 그냥 정렬을 해놓고 lower_bound를 돌려도 되고, 혹은 정렬을 해놓고 sweeping을 해서..

생각보다 시간이 많이 빠듯했다. 할 것도 많았고, 오랜만에 하다보니까 하나하나 생각하는데 시간도 꽤나 오래 걸렸다. 사실 애초에 이 셋에 일주일동안 쓴 시간이 다 합쳐봤자 얼마 안되었다는게 가장 문제였다. 18솔을 했다. 하지만 여왕벌은 거르더라도 실골 문제들을 풀자고 만들어 놓은 연습셋이 아니기 때문에 아쉬운 부분이 많다. 그래도 일단 쭉 정리를 해보려 한다 A - 사냥꾼 KOI 2013 고등부 1번 그냥 딱히 생각하는 것도 오래 안걸리고 구현도 딱히 안빡셌다. 무난한 문제 풀이 https://stonejjun.tistory.com/98 B - 막대기 KOI 2013 고등부 2번 문제를 잘 못봤다. 관찰 위주의 문제였고, 솔직히 오래 걸릴 문제도 아니었지만, 문제 조건을 잘못 봐서 오래 고생한것이 컸다..