https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net # 처음에 '스택'을 사용해서 풀려했지만, 생각보다 까다로워서 다른 방향으로 생각을 해봤다. # 결국 이 힌트처럼 양쪽에 더 높은 블록이 존재하면 빗물이 고인다. 따라서 반복문을 돌며 현재 블록의 왼쪽 값 중 최대높이, 오른쪽 값 중 최대높이를 구해 그 두 값중 작은 값이 현재 블록높이보다 크다면, 큰 값은 당연히 블록높이보다 크므로 작은 값 - 현재 블록 높이를 ans에 더해준..
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net # 투 포인터 기초문제이다. # left, right라는 포인터 두 개를 이용해 진행한다. 1. left를 0, right를 1로 초기 설정하고 num의 첫번째 값이 s이면 ans를 1부터 시작하고 아니면 s는 0으로 시작한다. 2. while문 안에서 left와 right포인터가 모두 N이라면 둘 다 맨 오른쪽(맨 끝)까지 간 것이므로 break 2-1...
https://www.acmicpc.net/problem/22114 22114번: 창영이와 점프 창영이는 버스에서 내린 뒤 회사로 걸어가고 있다. 창영이가 걸어가는 길은 대부분 회색 보도블럭으로 포장되어 있는데, 가끔씩 빨간 보도블럭이 놓여있을 때가 있다. 창영이는 어린 시절 빨간 www.acmicpc.net # 모든 케이스를 다 확인하기에는 N^2이 소요되어서 시간초과가 날 것이라 예상해 '투 포인터' 알고리즘을 사용해서 풀었다. (이 코드가 투 포인터가 맞나 싶긴한데...) 1. 반복문을 돌며 i가 N-1이거나 j가 N-1이 되면(마지막까지 도달한다면) break를 한다. 2-1. i, j를 0, 0으로 설정하고 L[j]가 K보다 작거나 같으면 cnt와 j를 1증가시킨다. 2-2. L[j]가 K보다 ..
https://www.acmicpc.net/problem/12761 12761번: 돌다리 동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대 www.acmicpc.net # "현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배나 B배의 위치로 이동을 할 수 있다." -> 동규가 이동할 수 있는 경우의 수는 다음과 같다. (현재 동규위치: x) (x+1, x-1, x+A, x-A, x+B, x-B, x*A, x*B, x*(-A), x*(-B)..
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 # 이분탐색 문제이다. (이분탐색 문제는 아이디어 떠올리기가 매우 힘든 것 같다..) # 집의 좌표가 0부터 10억사이이므로 그 사이에서 이분탐색으로 '간격' (가장 인접한 두 공유기 사이의 거리)을 찾아가면 된다. import sys input = sys.stdin.readline N, C = map(int,input().split()) wif..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net # 2017년 상반기 삼성 SW 역량 테스트 기출문제이다. # DP문제치곤, 그렇게 어렵지 않았다. # N일부터 1일까지 앞으로 가며 dp테이블을 갱신하는 코드: 1. 우선 arr[i][0] + i (현재 일수 + 상담에 걸리는 일수)가 N보다 크면 상담을 못하므로 dp[i]에 m을 넣어준다. 2. N보다 작을때 dp[i] = max(현재 상담을 완료하면 받는 금액(arr[i][1]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[arr[i][0] + i], m) 으로 갱신해준다. (m = 마지막날부터 계산할 때 현재까지의 최대 상..
https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net # 'N개의 행성을 터널로 연결하는데 필요한 최소비용' 보자마자 MST가 떠올랐다. # 처음에 N개의 행성 사이의 터널 건설비용을 모두 구한 뒤, 크루스칼 알고리즘을 사용하려 했다. 그런데, 모든 터널 건설비용을 구하기 위해선 N^2번의 연산이 필요하지만 N이 최대 10만이므로 이렇게 하면 시간초과가 발생한다. # A와 B 사이의 터널 건설비용은 min(|xA-xB..
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net # union-find로 푸는 방법과 BFS+이분탐색으로 푸는 방법 두가지가 있다. I. Union-Find 1. M개의 그래프정보를 입력받을 때 graph배열에 [-c, a, b]를 append해준다. (c = 중량제한, a = 시작 섬, b = 끝 섬) 아래 코드처럼 -c로 중량제한을 받은 뒤, sort해도 되고 c로 입력받은 뒤, 내림차순 so..
모르는 사이에 조금씩 조금씩..
