https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. Logic 빙산 주위에 붙어있는 물의 갯수 만큼 하루가 지나면 녹기 때문에 빙산위에서 상하좌우 4방향으로 존재하는 물의 갯수를 구한 후 갯수를 체크하는 배열에 갯수를 올려준다. 빙산이 두조각 이상 쪼개지면 답을 출력해야하기 때문에 답이 나오지 않는 이상 BFS가 끝나게되면 빙산 배열에서 녹아야 하는 물의 갯수를 빼주고 빙산이 녹는 시간(답)을 1++해준다. 녹는 빙산을 체크해주면서 동시..
Algorithm
https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 1. Logic - 스티커를 뜯으면 상하좌우 한개씩은 무조건 못사용하기 때문에 함수를 작성할때 이전에 어떤 스티커를 골랐는지, 어디 위치에 있는 스티커를 골랐는지 넘겨준다 DP table[어떤 스티커를 골랐는지][스티커의 index] 0 : 스티커를 안고르고 지나침 1 : 스티커의 y값이 0인 스티커를 선택 2 : 스티커의 y값이 1인 스티커를 선택 2. Code #include usi..
https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. Logic - 입력을 받으면서 가장 큰 값과 해당 값의 인덱스 번호를 저장해놓는다. - 저장해 놓은 가장 큰 값의 인덱스를 기준으로 앞에서부터 인덱스까지 돌며 빗물이 찼을 때 가장 최댓값을 구하고 똑같이 뒤에서부터 인덱스 까지 돌며 최대값을 구한다. 이후 각 블록의 높이를 다 더한값을 최댓값에서 빼주면 빗물의 총량을 구할 수 있다. 14719번 문제가 어렵다면 2304 창고..
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. Logic - 0에서부터 왔다가 돌아와서 책을 다시 가져가야 하기 때문에 모든 (경로값 * 2)를 하게된다. 그렇기 때문에 입력을 모든 값중 절댓값이 가장 큰 경로에 있는 책을 제일 마지막에 가져다 놓아서 * 2를 하지 않아야겠다는 생각을 했다. 1, 양수를 저장하는 positive배열과 음수를 저장하는 negative 배열을 받아서 각각 저장하며 절댓값을 통해 절댓값이 가장 큰 값을 저장해놓는다..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 1. Logic - 기본 BFS의 형식을 지켜 돌지만 for문을 돌게 되면 원하는 자리가 아닌 제일 처음 나오는 인덱스부터 돌기 때문에 완전탐색을 통해 Land의 모든 부분에서 돌아본 후 가장 최대값을 출력하면 된다. - 모든 인덱스에서 다 돌아봤을때 최대 시간 복잡도는 50 * 50 * 50 * 50 이 되므로 최대 6,250,000이 되어 1억을 넘지 않음으로 풀이 가능하다. 2. Code #in..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1. Logic 1. 1은 어떻게 계산 하던지 자기 혼자 더하는게 무조건 이득 2. 양수는 무조건 큰숫자부터 곱해서 더하고 혼자남으면 그냥 혼자 더히기 3. 음수는 절댓값이 큰 숫자부터 곱해서 더하고 혼자 남으면 그냥 더하기 or 0이 있으면 넘어가기 4. 0은 -1이 없거나 음수의 갯수가 짝수면 필요없지만 -가 홀수면 음수를 없애는데 사용 2. Code #include using namespa..
https://www.acmicpc.net/problem/1325 > n >> m; for(int i = 0; i > a >> b; vec[b].push_back(a); } for(int i = 1; i > m; for(int i = 0; i > a >> b; vec[b].push_back(a); } for(int i = 1; i
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. Logic - 처음엔 dp테이블을 2차원이라고 생각했지만 인덱스 갯수가 1500000이기 때문에 dp table이 2개가 아닌 한개라고 생각했다. - 부분문제를 쪼개봤다 1. 해당 날짜의 상담을 할때 - idx + 상담에 필요한 시간 + 상담으로 받은 상담비용 2. 해당 날짜의 상담을 안할때 - 상담을 안하고 다음 인덱스로 넘어가기 2. Code #include using namespace std; int n; vector vec; int dp[1500001]; int solve(int cur) { if(cur == n) ret..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1. Logic - Topdown 방식으로 풀이 현재 index에서 갈 수 있는 방향이 한정되어있기 때문에 아래의 좌우 로 한개씩 보내주고 리턴되는 값 중 최댓값을 대입한다. DP table : dp[몇번째 층인지][몇번째 숫자인지] 재귀를 타고 내려가면서 층수를 한개 올려주고 현재 노드의 인덱스와 같은 인덱스 한개 + 1한 인덱스 한개를 재귀로 보내줫다. 2. Code #include using namespace std; int n; int dp[501][501]; ..
https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 1. Logic - 카드를 최소한의 점수로 합체하기 위해서는 가장 작은 값끼리 묶어서 합쳐야 하기 때문에 우선순위 큐를 사용해서 가장 앞에 오는 두개의 수를 가지고 계산을 돌려준다! 2. Code #include using namespace std; priority_queue pq; int main() { long long n, cnt; cin >> n >> ..
