돌이 코딩하는 방

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

이번에는 자료구조의 성격을 띄고 있는 STL이 아닌 함수의 성질(?)을 띄고 있는 STL에 대해서 말하려고 한다. 바로 lower_bound와 upper_bound이다. lower_bound를 확실히 정리하려는 이유는 이상, 이하, 초과, 다음이 맨날 햇갈려서 항상 한번 긴가민가 하면서 코딩해보고 수정을 하기 때문이다. 엄청나게 시간소모를 하는것은 아니지만, 답이 틀릴때 마다 lower_bound에 확신이 없어 한 번 검토해야하는 것은 확실히 스트레스이다. ※ 배열은 1-base 기준입니다. lower_bound lower_bound는 범위내의 정렬된 자료들 내에서 원하는 원소보다 같거나 큰 첫 번째 위치를 찾아준다. 예를 들어서 벡터에 2 2 4 5 7 9가 있고, 이 벡터 전체에 대해서 7을 기준으로..

문제 링크 : 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. 어떤 칸에 ..

이 글에서는 Monotone Queue Technique(모노톤 큐 테크닉) 에 대해서 가볍게 다뤄보려고 한다. DP에서 사용하는 Monotone Queue Optimization에 대해서 알고 싶다면 이 글을 참고하자. What is Monotone Queue? Monotone Queue는 Monotone 과 Queue의 합성어이다. 즉 큐는 큐인데 단조로운 Queue라는 것이다. 즉, 어떠한 알고리즘을 토대로 큐를 단조롭게 관리하는 것이다. 당연히 큐를 단조롭게 관리함으로써 무엇인가를 얻을 수 있을 것이다. Problem 예시 문제로 BOJ 11003 최솟값 찾기를 가지고 왔다. 전체 n개의 숫자내에 속한 임의의 크기 k인 구간에 대해서 최솟값을 구하는 문제이다. Naive 하게 풀면 $O(NK)$,..

교내 경시를 대비하여 가볍게 돈 셋을 정리하는 글이다. Blackking26과 함께 7월 13일 19시 부터 20시 40분까지 100분 간 진행했다. 문제는 S5~G5 한글 디스크립션 랜덤문제 13문제를 뽑았다. 100분 동안 11문제를 풀었다. 실버라서 그런지 무난하게 빨리 풀렸다. 사실 좀 많이 쉬웠다. 앞으로는 난이도를 조금 올리는 게 좋을 것 같다. A. 삼삼한 수 어떤 수를 3진법으로 나타냈을 때 2가 있는지 확인하자. 예외 처리로 0을 신경써주어야 한다. 정말 간단하게 풀리는 문제 B. 텔레포트 어떤 두 도시를 가는 방법은 그냥 가거나, 출발지 -> 특별한 도시 -> 텔레포트 -> 목적지로 가는 두 가지 방법이 있다. 두번째 방법에서 텔레포트 비용은 항상 일정하기 때문에 모든 도시에 대해서 가..