BOJ
-
[10164] 격자상의 경로BOJ 2021. 9. 1. 20:24
https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net (1,1)에서 (N,M)까지 가는 경로의 경우의 수를 출력한다. 이때, 중간에 무조건 거쳐가야 하는 지점이 1개 존재할 수 있고, 아래쪽이나 오른쪽으로만 움직일 수 있다. 우선, 이동방향이 아래쪽 혹은 오른쪽으로 고정된 관계로, 모든 경우의 수는 최단경로이다. 일반적으로 상하좌우 모두 이동이 가능하다면, 최단경로가 P이고 왼쪽 혹은 위쪽으로 이동한 횟수가 Q일..
-
[1495] 기타리스트BOJ 2021. 9. 1. 20:12
https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 시작 값(S)이 주어지고, 여기에 a[i]만큼 더하거나 빼는 과정을 N번 반복한다. 이 과정중 값은 항상 0이상 M이하이여야 하고, N번 반복한 후의 최대값을 구해야 한다. dp를 다음과 같이 구성하자. dp[i][j] : i번 더하거나 빼서 j를 만들 수 있는 경우, true. 아니라면 false 입력은 dp[0][s]=true로 표현할 수 있고, 찾는 값은..
-
[2252] 줄 세우기BOJ 2021. 8. 31. 01:02
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 입력은 노드의 개수, 간선의 개수와 방향그래프가 들어온다. a가 b보다 키가 크고, b가 c보다 키가 큰데 c가 a보다 키가 클수는 없다. 한마디로 입력은 곧 DAG이고, 위상정렬을 사용할 전제조건이 충족된 셈이다. 이후로는, 그냥 위상정렬을 해주어 출력하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..
-
[1655] 가운데를 말해요BOJ 2021. 8. 31. 00:55
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net N : 10만, 시간제한 0.1초로 사실상 O(n)이하의 시간복잡도를 갖는 풀이를 구상해야 한다. 입력을 받자마자 상수시간내에 중간값을 계산해야 한다는 생각은 했지만, 정작 처음에는 우선순위큐도 생각이 안났다. 일반적으로 2개의 우선순위큐를 만드는데 하나는 오름차순, 하나는 내림차순으로 만든다. 최대힙과 최소힙을 만들고, 아래의 규칙을 지키도록 입력된 숫자를 적절한 곳에 넣으면 된..
-
[16975] 수열과 쿼리 21BOJ 2021. 8. 31. 00:40
https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 느리게 갱신되는 세그먼트 트리 문제이다. 느리게 갱신하는 이유는, '구간'으로 업데이트가 이루어지기 때문이다. 당장 필요한 구간이 아니라면 바로 업데이트하지 않고, 꼭 필요할때까지 업데이트를 미루는것이 기본 세그트리와 다른점이다. 일반적인 세그먼트 트리에서 T개의 구간을 갱신하려면, TlogN의 시간복잡도가 나올것이다. 만약 입력이 아래와 같다고 생각해보자. 2~n까지 1을 더..
-
[12920] 평범한 배낭 2BOJ 2021. 8. 31. 00:22
https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 냅색문제는 물건의 개수가 1개 혹은 무한대일때에는 쉽게(?) 풀린다. 어쨋든 웰노운이니까.. 그런데 물건의 개수가 2개, 3개같이 애매한 숫자라면 의외로 어려워진다. 물론 2개라면 물건의 개수만 2배로 넣어주면 되지만, 이 문제는 물건의 개수를 하나씩 분할해서는 풀 수 없다.(TLE) 그렇기에 이 문제의 일반적 해법은 2진수꼴로 물건을 분할하는, 비트마스킹..
-
[12865] 평범한 배낭BOJ 2021. 8. 31. 00:06
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색은 3종류가 있다. 1) 물건의 개수가 무한대인 경우 -> DP로 해결한다. 가장 일반적인 형태인듯 싶다. 2) 물건의 개수가 1개인 경우 -> DP로 해결한다. 1번과는 다르지만, 사실 코드는 매우 유사하다. 3) 물건을 쪼갤 수 있는 경우 -> Greedy로 해결한다. 매우 직관적인 Greedy라 1,2번에 비해서 쉽다. 이..
-
[14003] 가장 긴 증가하는 부분 수열 5BOJ 2021. 8. 30. 23:56
https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net O(NlogN)에 최적해 역추적까지, 가장 긴 증가하는 부분수열 1~5를 모두 포함하는 문제라 할 수 있겠다. lower_bound를 써서 적절한 위치를 O(logN)만에 찾고, 이를 '오름차순'을 유지하도록 넣어주면 된다. 오름차순을 유지하지 못하면, 당연히 이분탐색 기반의 lower_bound도 사용할 수 없기 때문이다. 또한, 우리는 하나의 입력을 받고 그 입력..
-
[2206] 벽 부수고 이동하기BOJ 2021. 8. 30. 22:20
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 맵의 크기가 최대 1000*1000일때, (1,1)에서 (N,M)까지의 최단거리는 매우 간단하게 구할 수 있다. 이 문제는 지나갈 수 없는 벽을 1회 부술 수 있다는 조건이 붙어있고 이로인해 기본적인 bfs와는 다른부분이 몇개 존재한다. 예를들어, 아래와 같은 경우를 보자 5 5 00000 11100 00001 01011 11010 (1,1)에서 (3,3)까지의 최단경로는..
-
[14428] 수열과 쿼리 16BOJ 2021. 8. 30. 22:00
https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net 최소값을 찾는 세그먼트 트리를 구현하고, 값 대신 인덱스를 리턴하도록 만들면 된다. 리프노드에는 인덱스가, 그 외에는 구간중 최소값을 갖는 인덱스가 들어가도록 구성한 다음에, 인덱스를 리턴하는 부분을 처리하기 위해 minIdx라는 함수를 만들었다. 단순히 최소값을 리턴하는 문제라면, (left>end || right