https://www.acmicpc.net/problem/10800 공의 개수가 최대 20만 개, 색상 수도 최대 20만 개, 크기는 최대 2천 가지라 어떻게 해결해야 할지 고민을 좀 많이 했다.크기 순으로 정렬을 하더라도, 같은 색상의 공들은 빼야 하고, 같은 크기를 가지는 공들도 제외해야 한다. 이를 해결하기 위해 같은 색상 공들의 크기 합, 같은 크기를 가지는 공들의 크기 합을 따로 보관해야겠다고 생각했다.같은 색상 공들의 크기를 따로 보관하면, 전체 공 크기의 합에서 같은 색상 공들의 크기 합을 빼 해당 공의 점수를 구할 수 있게 된다.같은 크기를 가지는 공은 순회하면서 앞의 공과 크기가 달라질 때마다 비워주면서 전체 공의 크기 합, 같은 색상 공들의 크기합을 누적하도록 했다. 로직 순서1. 색..
분류 전체보기
2655번: 가장높은탑쌓기첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차www.acmicpc.net 문제를 보고 생각난 풀이는 백트래킹, 추적할 수 있는 DP 두 가지였다.하지만 벽돌의 수가 최대 100개이기 때문에 백트래킹으로 풀이할 경우 시간 초과가 날 것이라 제외했다. 문제 조건을 보면, 각 벽돌의 밑면 넓이와 무게는 모두 다르다.나는 무게를 기준으로 삼아 내림차순으로 벽돌을 정렬했다. DP 테이블을 만들어가며 추적까지 가능하도록 pair를 사용해서 테이블을 만들었다.std::pair dp[101]; // {total_height, from} DP[..
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지형의 탐사 가치가..
2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 처음에는 그냥 DFS 돌리면 되지 않을까?라고 생각했는데 시간초과가 났다;; 메모이제이션을 적용 dp[i][j][k] : (i, j)칸이 주어진 영단어의 k번째 알파벳으로 위치할 수 있는 경우의 수 메모이제이션을 적용하고도 계속 시간초과가 나서 왜 그런가 고민하다가 질문 게시판을 확인했는데, dp 배열을 -1로 초기화하지 않은 것이 문제였다. dp 배열을 0으로 초기화하면 생기는 문제 (i, j)칸이 주어진 영단어의 k번째 ..
