전체 글
-
[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
-
[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