본문 바로가기

분류 전체보기140

[백준] 17831 - 대기업 승범이네 https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net tree DP 문제이다. 어떤 부모-자식 관계의 노드 2개의 쌍들을 만들어서 그 쌍들의 곱의 합의 최댓값을 구하는 문제이다. 본인은 dp 배열을 다음과 같이 정의하였다. dp[i][j] = i번째 노드가 (j == 1이면 멘토, j == 0이면 멘토가 아닐 때), i 번째 노드를 포함한 서브트리의 시너지의 최댓값 따라서 j가 1일때와 0일 때를 나누어서 생각해 보자... 2023. 1. 16.
[백준] 1749 - 점수따먹기 https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 2차원 행렬에서의 누적합을 이용하는 문제이다. 먼저 누적합 배열 sum을 채워 넣어보자. (1, 1)부터 (i, j)까지의 직사각형의 누적합을 나타내는 sum[i][j]는 어떻게 구할 수 있을까? 바로 sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; 마지막에 -sum[i - 1][j - 1]을 하는 이유는, sum[i - .. 2023. 1. 16.
[백준] 20188 - 등산 마니아 https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 이 문제는 서로 다른 정점 i, j를 골랐을 때 i -> 1 -> j 또는 j -> 1 -> i로 가는 경로 중 가장 짧은 경로에서 거치는 오솔길의 개수를 구하는 문제이다. N의 제한이 30만이므로 N^2에 해결할 수 없다. 이 문제는 발상의 전환을 해서 O(N)으로 해결할 수 있다. 바로 간선의 입장에서 생각해보자. 바로 빨간 간선의 입장에서 생각해 보자. 이게 무슨 말이냐? 바로 빨간 간.. 2023. 1. 12.
[백준] 20183 - 골목 대장 호석 - 효율성 2 https://www.acmicpc.net/problem/20183 20183번: 골목 대장 호석 - 효율성 2 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net int overflow와 부등호 때문에 많은 애를 먹었던 문제이다. 핵심은 파라메트릭 서치 + 다익스트라이다. 파라매트릭 서치의 매개 변수로, 지나온 경로의 최대의 최소를 정한다. 이후 각 이분 탐색마다 지정한 제한을 넘지 않게 다익스트라를 돌리면 된다. 이분 탐색에서 초기 left와 right는 어떻게 정해야 할까? 생각해 보면 모든 답은 -1 또는 주어진 .. 2023. 1. 11.
[백준] 1711 - 직각삼각형 https://www.acmicpc.net/problem/1711 1711번: 직각삼각형 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,500)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 좌표값은 절댓값이 1,000,000,000을 넘지 않는 정수이며, 주 www.acmicpc.net 이 문제는 N제한이 1500이고, 1500C3 = 약 5억 6천 이므로 어떻게 커팅을 잘하면 시간제한 5초 안에 해결할 수 있다. 하지만 커팅 과정도 번거롭고 커팅 이후에도 통과가 되지 않을 수 있으므로 유의하며, 다른 방법으로 풀어보자. 먼저 직각 삼각형의 정의를 살펴보면, 한 각이 직각인 삼각형이다. 세 점을 어떻게 골랐다 쳐도, 직각인지를 판단해야 한다. 이제부터.. 2023. 1. 11.
[백준] 1445 - 일요일 아침의 데이트 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 이 문제의 난이도가 골드 2로 측정된 이유는 국어 능력 때문이라고 생각한다.. 쓰레기가 있는 칸('g')은 인접한 칸에 쓰레기가 있던 없던 상관하지 않는다. 즉, 인접한 칸에 쓰레기가 있는 칸을 판단하려면 해당 칸에 아무것도 없어야('.')한다. 그래서 쓰레기 칸인지 판단하는 isGarbage()와 인접한 칸에 쓰레기가 있는지 판단하는 isAdjecant()를 작성하였.. 2023. 1. 10.
[백준] 13905 - 세부 https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 어떤 하나의 가중치 연결 그래프가 주어지고 출발점에서 끝점까지 가는 경로 중, 지나가는 경로의 가중치 중 최솟값의 최대를 구하는 문제이다. 사실 말로만 하면 문제 이해가 어려울 수 있으니 문제를 직접 보는 것을 추천한다. 즉, 이러한 그래프에서 1 -> 5로가는 경로를 찾는다고 해보자. 1 -> 2 -> 3 -> 5 1 -> 7 -> 3 -> 5 1 -> .. 2023. 1. 7.
[백준] 16927 - 배열 돌리기 2 https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 배열과 인덱스에 매우 약한 지라, 이 문제는 상당 시간 걸렸던 것 같다. 문제의 핵심은 현재 회전할 위치의 번호가 가장자리에서부터 얼마나 떨어져 있느냐이다. 그리고 본인은 이것을 "껍데기"라 표현하겠다. 그렇다면 껍데기를 어떻게 구할 수 있을까? n과 m이 다르므로, 다음과 같이 구할 수 있다. min(.. 2023. 1. 3.
[백준] 2469 - 사다리 타기 https://www.acmicpc.net/problem/2469 2469번: 사다리 타기 첫 줄에는 참가한 사람의 수 k가 나온다(3 ≤ k ≤ 26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3 ≤ n ≤ 1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정 www.acmicpc.net 일반적인 사다리 게임에서 시작 값과 결과 값을 알려주고 숨겨놓은 가로 한 줄을 찾는 문제이다. 문제를 처음 볼 때는 오직 가로 한 줄만 숨겨져 있기 때문에 브루트포스로 해결할까 생각했지만, 숨겨진 가로 한 줄의 경우의 수 -> 수백 ~ 수천만 하나의 경우 당 사다리 타기 시간 복잡도 -> O(kn) k는 최대 26, n은 최대 1000이므로 시간초과가 날 것이 뻔했다. .. 2023. 1. 3.

티스토리툴바