https://www.acmicpc.net/problem/10800 공의 개수가 최대 20만 개, 색상 수도 최대 20만 개, 크기는 최대 2천 가지라 어떻게 해결해야 할지 고민을 좀 많이 했다.크기 순으로 정렬을 하더라도, 같은 색상의 공들은 빼야 하고, 같은 크기를 가지는 공들도 제외해야 한다. 이를 해결하기 위해 같은 색상 공들의 크기 합, 같은 크기를 가지는 공들의 크기 합을 따로 보관해야겠다고 생각했다.같은 색상 공들의 크기를 따로 보관하면, 전체 공 크기의 합에서 같은 색상 공들의 크기 합을 빼 해당 공의 점수를 구할 수 있게 된다.같은 크기를 가지는 공은 순회하면서 앞의 공과 크기가 달라질 때마다 비워주면서 전체 공의 크기 합, 같은 색상 공들의 크기합을 누적하도록 했다. 로직 순서1. 색..
백준
2169번: 로봇 조종하기첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.www.acmicpc.net 그냥 아래, 오른쪽만 갈 수 있었으면 묻지도 따지지도 않고 'DP구만'하고 풀었겠지만,왼쪽으로도 갈 수 있다는 조건 때문에 DP를 사용하되, 어떻게 풀이할까 고민했다. DP 배열을 주어지는 지형과 같이 2차원으로 구성할까 했지만 각 방향에서 해당 칸으로 오는 경우들을 고려하기 위해서3차원 배열로 구성했다. int dp[1002][1002][3]; // from left, from up, from right지형의 탐사 가치가..
13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 그리디 문제만 보면 지능이 낮아지는 병이 있어서 힘들게 풀었다 그리디인건 빠르게 눈치챘는데, 어떻게 풀어야 할지 모르겠어서 질문 게시판의 반례를 쳐다보다 아이디어를 얻었다. 마감일이 N일 남은 문제는 N일 전에만 해결하면 된다. 마감일이 4일 남은 문제는 1일 차에 하든, 2일 차에 하든, 3일 차에 하든, 4일 차에 하든 상관없단 거다. '1일 차부터 N일차까지 현재 과제를 집어넣을 수 있는 날이 있는가?'를 따져보고 넣을 수 있다면 답에 점수를 더하자 작년에 푼 이 문제와 상당히 유사하다. 10775번:..
2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 분명 쉬운 문제인데 오래 걸렸다. 문제 분류를 보니 스택도 있던데, 나는 그냥 구현으로 해결했다. 1. 우선 정보를 입력받고, L(왼쪽 면의 위치)을 기준으로 오름차순으로 정렬한다. 2. 최고 높이를 가진 기둥을 찾아 그 기둥의 인덱스를 기록해 둔다. 3. 0부터 최고 높이를 가진 기둥의 인덱스까지 오름차순으로 검사. 3-1. 이전 최고 높이보다 높거나 같은 높이를 가진 기둥을 찾을 때마다 넓이를 정답에 더하고, H와 L을 갱신. 4. 마지막 인..
