문제https://www.acmicpc.net/problem/15486 어떻게 풀 것인가?주어진 날짜와 수익 배열을 통해서 최대 수익을 낼 수 있는 경우를 찾으면 되는 문제였다. 해당 문제는 Bottom-up 방식으로 1일부터 차례대로 최댓값을 갱신해주도록하면서 풀었다. 1일차 (N==1)dp[1] = 0, // 1일에 얻을 수 있는 최대 금액 (max) // 다음날 nxt = 1 + T1 = 4 dp[4] = Math.max( dp[4], dp[1] + P1) = 10 // 1일을 마치고 4일에 얻은 최대 금액 10 저장 2일차 (N==2)dp[2] = 0, // 2일에 얻을 수 있는 최대 금액 (max) // 다음날 nxt = 2 + T2 = 7 dp[7] = Math.max( dp[7], dp..
문제 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 어떻게 풀 것인가? 이번 문제도 빡 구현이었다. 사실 문제를 처음에 읽었을 때는 그다지 어렵지않다고 생각을 하였으나, 이번에도 생각보다 조건이 까다롭다고 느꼈다. 특히나 2번 빨간색일때, 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다. 이 부분을 해결하기 위해서 전체적으로 자료구조를 뒤엎어야만 했다. 그 외 부분은 읽으면서 코드로 옮긴다면..
문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 어떻게 풀 것인가? 사실 문제 자체가 길고, 너무 난해해서 어려웠던 문제 하지만, 문제를 이해하고 시키는 조건들을 코드로 바꾼다면 그리 어려운 알고리즘은 없는 그런 문제였다. 즉, 정말 빡센 브루트포스 + 구현 문제였다. 경계선을 구하기 위해서 단지 모든 경우의 수를 계산해야하만 한다. 즉, X,Y,D1,D2 모두를 4중 For문을 통해서 계속해서 경우의 수 모두를 검증하고 답을 찾는 문제였다...
문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 어떻게 풀 것인가? 구현은 너무나도 어렵다. 특정 알고리즘은 외우면 된다지만, 구현은 생각해야할 것들이 너무나도 많다. 이번 문제는 큐를 이용한 구현 문제였다. 내가 푼 문제의 코드를 뜯어보자. 다리는 Queue로 선언해 준고 여기에 다리의 길이만큼 0을 넣어준다. 다리의 길이만큼 이동하면서 Queue를 계산하게 된다 Queue bridge =..
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 어떻게 풀 것인가? 처음에 감조차도 못잡았던 문제였다. 대략 1시간정도의 고민 끝에 다른 분의 풀이를 참고했다. 아마 이번 포스팅은 풀이보다는 회고 느낌으로 작성을 해야할 것 같다. 이 문제는 "이분탐색"을 물어보는 문제였다. 그렇다면 이러한 이분탐색을 어디에 활용할 수 있었을까? '최소 거리에 대해 설치 가능한 공유기'가 문제에서 주어지는..
문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 어떻게 풀 것인가? 문제를 읽었을 때, 빠르게 BFS를 떠올렸다. 하지만 문제는 말의 이때 단순히 visited배열을 2차원으로 선언해 주면 인접 노드로 이동했을 때와 말이 이동할 수 있는 위치로 이동했을 때 서로 다른 경로로 방문했지만 이를 구별할 수 없어 무조건 한번 방문한 곳은 다시 방문할 수 없다는 점을 발견했다. 그래서 이 부분에 대해서 골똘히 고민을 하다가 결국엔 ..
문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 어떻게 풀 것인가? 문제를 처음 읽어보신 분들이라면 아마, 문제가 해괴하다고 느낄지 모른다. 적어도 나는 그랬다. 처음에 문제를 읽었을 때 좌표 개념이 나와서 BFS나 DFS를 생각했다. 하지만 결국엔 문제가 풀리지 않아서, 다른 분의 풀이를 참고하고 나서 단순 구현 및 시뮬레이션 문제라는 점을 발견했다. 문제를 읽었을 때 가장 어려운 부분은 아마 "다음 N-1세대..
문제https://www.acmicpc.net/problem/14719 14719번: 빗물첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치www.acmicpc.net 어떻게 풀 것인가?우리가 흔히 말하는 빡구현 문제이다. 현재 블록의 높이보다 높은 블록이 왼쪽에 있어야 한다. 현재 블록의 높이보다 높은 블록이 오른쪽에 있어야 한다. 첫, 마지막 블록에는 빗물이 고일 수 없다.인덱스 별로 모이는 빗물의 정보를 더해준 다음 출력해주면 된다. 현재 인덱스를 기준으로 왼쪽에서 가장 높은 블럭과 오른쪽에서 가장 높은 블럭을 구해준 다음, 현재 블럭이 ..
