본문 바로가기

분류 전체보기

 (236)
C++[백준]3273번 두 수의 합 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 솔루션 수열이 있을 때 i와 j의 합이 x가 되어야 한다는 조건 때문에. 나는 정렬과 이분탐색을 떠올렸다. 정렬을 한 뒤, i라는 수를 선택했을 때, i+1과 N 사이에 이분 탐색으로 하여 idx를 찾는다. i와 배열 사이에 있는 idx를 더했을 때 X와 같다면 갯수를 세어주었다. 코드 #include #include using namespa..
C++[백준]14465번 소가 길은 건너간 이유 5 https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 솔루션 스위핑? 이라고 해야 하나? 먼저 K를 구간이라고 생각하고 문제를 접근했다. 특정 구간 i에선 [i-K] ~[i] 라는 구간에 고장 난 신호등의 개수가 가장 작은 값을 저장하면서 해결했다. 먼저 i=1;i N >> K >> B; for (int i = 0; i > idx; visit[idx] = true; } int cnt = 0; int ans = B; for (int i = 1; i
C++[백준]2307번 도로검문 https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리 www.acmicpc.net 솔루션 다익스트라의 응용 문제인 것 같다. 먼저 용의자가 갈 수 있는 가장 빠른 길을 다익스트라를 통해 찾아준다. 이 때, 값이 갱신될 때 마다 부모노드. 즉 어떤 노드에서 해당 노드로 왔는지 기록을 한다. 이렇게 다익스트라를 한 번 수행하면, 용의자가 이용하는 가장 빠른 경로를 찾을 수 있다. 경찰이 검문을 해야 하는 후보는 가장 빠른 경로중 하나이다. 경로 쌍을 방문하지 못하도록 조건문을 걸고, 도..
C++[백준]11728번 배열 합치기 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 솔루션 A배열과B배열의 입력을 다 받고, 두 변수 i,j를 선언한다. 그리고 i 는 A배열의 사이즈보다 작고, j는 B배열의 사이즈보다 작을 동안 i와 j중 더 작은 수를 출력하고 i를 출력했다면 i++ j를 출력했다면 j++ 을 해 주고 만약 i, 또는 j가 출력이 다 되어서 while이 끝난다면, i가 A배열보다 작은 동안 출력. j가 B배열보다 작은 동안 ..
C++[백준]16198번 에너지 모으기 https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 솔루션 나는 완전탐색+dfs로 해결을 했다. 먼저 N을 입력을 받고, 시작점은 1, 끝점은 9이하인 수 중에서 방문하지 않았던 수 사이를 for문을 돌았다. 각 for문은 방문하지 않았다면, 왼쪽에서 나타난 값 * 오른쪽에서 나타난 값 + dfs 를 재귀적으로 해 주었다. 코드 #include #include using namespace std; int N; int arr[11]; bool ..
C++[백준]16968 차량 번호판 1 https://www.acmicpc.net/problem/16968 16968번: 차량 번호판 1 00부터 99까지 총 100가지 중에서 00, 11, 22, 33, 44, 55, 66, 77, 88, 99가 불가능하다. www.acmicpc.net 솔루션 알파벳이 가능한 경우의 수는 26, 숫자가 오는 경우의 수는 10가지 이다. 그런데, cc또는 dd가 오는 경우 이전과 같은 문자는 쓸 수 없기 떄문에 아래와 같은 경우는 -1을 해서 곱해준다. 코드 #include using namespace std; string str; int arr[4]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> str..
C++[백준]20040번 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 솔루션 처음에.. 모든 노드를 다 둘러서 다시 시작점으로 와야 하는 줄 알고 착각하고.. 문제 어렵다 생각했는데, 문제를 다시 보니, 특정 점에서 얼만큼 방문하던, 다시 특정 점으로 오면 된다고 한다. (이래서 글을 유심히 읽어야 한다.) 그래서 생각을 해 낸 것이, UnionFind이다. 각각의 선분을 그을 때, 이를 하나의 집합으로 연결 시킨다. 이 때, 선분을 그었는데, 이미 같은 집합..
C++[백준]1781번 컵라면 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 솔루션 처음에 데드라인이 가장 늦게 끝나는 것 부터 채워 오다가 시간초과를 받았다. 그래서 떠 올린 방법이 우선순위 큐 2개를 이용해서 푸는 방법이다 아직 처리 안한 문제를 담은 pq1 - 데드라인이 빠른 것 부터, 같다면 컵라면 수를 많이 주는 것부터 내가 처리한 문제들을 담은 pq2 - 컵라면의 개수가 가장 낮은 것부터 (이때 deadline은 상관 없을 것 같다.) for문을 i를 통해서 1일부터 N..

티스토리툴바