BOJ
-
[6549] 히스토그램에서 가장 큰 직사각형BOJ 2021. 8. 30. 21:42
https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 세그먼트 트리를 이용했다. 리프노드에는 각 직사각형의 높이를 저장하고, 리프노드가 아니라면 구간중 가장 작은 높이를 저장한다. end-start+1이 느리게 갱신되는 세그먼트 트리랑 겹치는 부분이 있지만 이 문제는 lazy propagation은 아니고, 구간중 가장 짧은 높이는 세그먼트 트리로, end-start+1으로 가로길이를 구해 직..
-
[15685] 드래곤 커브BOJ 2021. 8. 30. 17:46
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 그림만 보다보면 답이 안보인다. 드래곤커브를 회전시키는거에 집중하지 말고, 드래곤커브의 방향의 규칙성을 파악해야 쉽게 풀린다. 예제의 순서대로 방향을 아래와 같이 정의하자. 우/상/좌/하 : 0 / 1 / 2 / 3 또한, 우리가 필요한건 1*1의 정사각형을 이루는 네 개의 점이 모두 드래곤커브의 '일부'인 경우의 수이므로, 세대나 방향같은 부가적인 정보는 굳이 맵에 담..
-
[10451] 순열 사이클BOJ 2021. 8. 30. 17:15
https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 입력은 방향그래프가 들어온다. 아래와 같이 들어오면 3을 출력하면 된다. 예제의 두번째 그래프는 아래와 같다. 자기 자신을 가리키는 노드는 그림에는 없지만, 5개로 그림의 2개와 더해 7이 정답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..
-
[1303] 전쟁 - 전투BOJ 2021. 8. 30. 17:06
https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 기본적인 BFS 문제에서, 입력이 붙어있는 문자열이고, W와 B모두 각각 탐색하고 각각의 위력의 합을 출력해야 한다. W로 bfs가 시작되면 W만 탐색하고, B로 bfs가 시작되면 B만 탐색해야 하며 입력을 int로 변환하든, char을 그대로 사용하든 그 두개가 헷갈리지 않게만 주의하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..
-
[5557] 1학년BOJ 2021. 8. 30. 16:58
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 6 5 2 1 4 1 7 같은 입력이 들어오면, 5 - 2 - 1+ 4 + 1 = 7 처럼 n-1개의 수를 더하거나 빼 n번째 숫자를 만들 수 있는 경우의 수를 세야한다. 이와 더불어, 왼쪽부터 차례대로 계산할때 값이 항상 0이상 20이하인 경우의 수만 세야한다. 다이나믹으로 해결할 수 있는 문제이고 dp[i][j]에서 i를 숫자의 개수, [j]를 숫자의 값으로 놓으면 우리가 구해야하는 답..
-
[2212] 센서BOJ 2021. 8. 30. 16:45
https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net n개의 데이터를 k개의 집합으로 분할하고 분할된 각 집합의 (최대값)-(최소값)의 총합을 최소화하는 문제이다. 6 2 1 6 9 3 6 7 입력이 위와 같을때, 센서들의 위치를 정렬한 뒤 중복을 제거하면 아래와 같다. 1 3 6 7 9 이를 {1, 3}, {6, 7, 9}처럼 분할하면 (3-1)+(9-6)=5의 최적해를 얻을 수 있다. 또한, k>=n인 경우에는 모든 데이..
-
[1932] 정수 삼각형BOJ 2021. 8. 24. 06:03
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2차원 dp 문제이다. dp[i][j]=i행에서 j번째 수를 선택할때의 최대값으로 채워주었고, O(n^2)만에 해결할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include using namespace std; int a[501][501], dp[501][501]; int main(void) { int n, i, j; scanf("%d", &n); for (i = 1; i