돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/1591 문제 풀이 맨 처음에 같은 숫자의 가능성을 생각하지 못하고, 배열에서 인접한 두 값을 통해서 순서 관계를 얻을 수 있기 때문에 이를 조합하여 위상정렬을 하면 될 것이라고 생각했다. 그래서 코딩을 바로 했고, 틀린 후에 같은 숫자의 가능성을 생각해냈다. 일정 시간동안 생각을 했음에도 풀이를 생각해 낼 수 없었고, 태그를 열어봤더니 오일러 경로가 있었다... 몰랐던 내용이었기 때문에 풀이를 보았다. 길이 m-1 개의 배열로 잘라서 생각한다. 그 m-1 길이의 배열간의 배치 순서를 모두 알 수 있다면 문제를 해결할 수 있다. 문제에서 주어지는 길이 m의 배열은 길이 m-1 배열 두 개의 인접한 순서 관계를 알려준다. 정확히는 맨 ..

문제 링크 : https://www.acmicpc.net/problem/16056 문제 풀이 문제에서 주어진 정보를 그래프처럼 생각하면 정점을 가구와 콘센트 두 종류로 분류할 수 있다. 그리고 모든 간선은 가구와 콘센트 사이만을 잇는다. 즉, 이분그래프가 나오게 된다는 것이다. 그리고 최대 매칭값을 비슷하게 구하는 문제이기 때문에 이분 매칭을 떠올릴 수 있다. 이 문제의 가장 큰 특징은 하나의 콘센트에만 멀티탭을 꽃아서 3개의 가구와 연결을 시킬 수 있다는 것이다. 생각을 해보자. 한번 이분매칭 했을 때 추가로 이을 가구가 존재하지 않는다면 그대로 답이 될 것이며, 연결이 되지 않은 두 개의 가구가 같은 콘센트에 매칭이 될 수 있으면 그 콘센트에 플러그를 꽃아 2개의 추가매칭을 만들 수 있다. 그렇지 않..

문제 링크 : https://www.acmicpc.net/problem/2802 문제 풀이 K개를 골랐을 때 최솟값을 구하는 문제... 문제를 딱 보면 최솟값을 구하는것이 아니라 특정 x값 이내가 되도록 k개를 고를 수 있는지에 대한 결정 문제로 변화시켜야 된다는 감을 잡을 수 있다. 즉, 파라메트릭 서치를 사용하면 될 것이라는 것이다. 파라매트릭 서치를 사용한다고 치자. 어떤 m*m*m 범위가 존재하여 그 안에 k개가 있는 그러한 범위가 있는지를 빠르게 판별해야 한다. 위치가 바뀌지 않으니까, prefix sum을 이용하면 된다. 3차원 이기 때문에 포함과 배제의 원리와 prefix sum을 잘 이용하면 m*m*m 큐브 범위내의 수를 셀 수 있다. 구현이 살짝 까다롭다. 1차이 관리가 살짝 까다로우며 ..

문제 링크 : https://www.acmicpc.net/problem/1989 문제 풀이 수열에 있는 각 수 별로 그 수가 최솟값인 최대 배열을 잡을 수 있으면 문제를 풀 수 있다. 옛날에 풀었던 문제가 생각났고, 풀이가 바로 생각났다. 어떠한 수열 조각에 대해서 최솟값을 잡는다. 그럼 그 때 그 최솟값에 대한 값은 그 값 * 수열 조각의 구간합이다. 이때 다른 임의의 값은 그 최솟값을 포함하면 그 값이 최솟값이 될 수 없다. 따라서 수열 조각에서 최솟값 부분을 빼면서 수열을 쪼갤 수 있다. 이런식으로 수열을 계속 쪼개나가면서 값을 구하면 된다. 구간 최솟값과 구간 합은 둘다 segment tree를 이용하여 구할 수 있다. 그리고 구현이 더 쉬운 다른 풀이가 생각났다. 결국 수열의 모든 값에 대해서 ..

일시 : 8.13 문제 : 1989 부분배열 고르기 2 난이도 : P5 태그 : 미확인 풀이 : 미확인 풀이 시간 :

Project - Random Platinum Defense. 당신은 플레티넘 문제를 한 시간 안에 풀 수 있습니까? 그 어떤 플레티넘 문제라도? 플로우, 기하, 혹은 문자열이라도? 정수론, 애드 혹, 혹은 RPG EXTREME 이라도? 기본기가 약한 나를 위한! 문제를 편식해서 푸는 나를 위한! 문제를 끝까지 마무리 짓는 능력이 부족한 나를 위한! 문제를 푸는 속도가 느려진 나를 위한! 랜덤 플레 디펜스! 지금 바로 시작합니다! 실행 방법 1. sovled.ac 를 이용해 랜덤한 플레티넘 단계의 문제를 선정한다. 2. 한시간(조정 가능) 동안 문제 읽기 시작부터 해결까지 마무리 짓는다. 3. 만약 일정 시간 동안 풀이를 떠올리지 못한다면 태그를 보고. 고민하고, 풀이를 보고 업솔빙을 진행한는 것을 순차..