https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. Logic 음수와 양수가 섞여있기 때문에 먼저 오름차순으로 정렬을 한다. 두개의 포인터중 하나는 음수에서부터 하나은 양수에서 부터 서로 끝과 끝에서 가운데로 모이는 방식으로 투포인터를 적용한다. 2. Code #include using namespace std; const long long INF = 1e12; vector ans(2); vector vec;..
백준 풀이
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1. Logic - 인덱스를 가르키는 두개의 포인터 변수(start, end)를 선언 한 뒤 원하는 수보다 sum이 작으면 다음 배열로 end를 옮기고 vec[end] 더해주고 크면 vec[start]를 빼주고 start 포인터를 하나 더해준다. Testcase 하나를 예시로 들어보면 Testcase 10 4 5 1 3 5 10 7 4 9 2 2 여기서 더해서 4가 되는 연속되는 인..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. Logic 빙산 주위에 붙어있는 물의 갯수 만큼 하루가 지나면 녹기 때문에 빙산위에서 상하좌우 4방향으로 존재하는 물의 갯수를 구한 후 갯수를 체크하는 배열에 갯수를 올려준다. 빙산이 두조각 이상 쪼개지면 답을 출력해야하기 때문에 답이 나오지 않는 이상 BFS가 끝나게되면 빙산 배열에서 녹아야 하는 물의 갯수를 빼주고 빙산이 녹는 시간(답)을 1++해준다. 녹는 빙산을 체크해주면서 동시..
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/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]; ..
