💕
후원
본문 바로가기

Algorithm/Problem Solving8

[BOJ] 15647. 로스팅하는 엠마도 바리스타입니다 https://www.acmicpc.net/problem/15647트리의 각 노드에서 다른 모든 노드로 가는 최단 경로들의 합을 구하는 문제입니다.간단하게 생각해서 각 노드가 다른 노드로 갈 때 무조건 루트 노드를 거친다고 가정하고 계산한 후 필요없는 간선을 빼주면 될 거라고 생각했습니다.len_to_root = [0 for _ in range(N + 1)] # 루트 노드에서 각 노드로 가는 거리len_to_parent = [0 for _ in range(N + 1)] # 부모 노드로 가는 거리parents = [0 for _ in range(N + 1)] # 부모 노드subtree = [0 for _ in range(N + 1)] # 서브트리 개수def dfs(now, parent, length): .. 2024. 6. 26.
[BOJ] 1629. 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 간단하게, A의 B제곱을 구하는 문제입니다. B의 값이 매우 클 수 있으므로, DP를 이용합니다. A의 n제곱을 모두 저장하여 사용하기에는, 계산값을 저장하는 배열의 크기가 2,147,483,647이 될 수는 없으므로 다른 방법을 생각해봅니다. B를 2진수로 바꾸어서, 예를 들어 29라면 11101(2)를 생각해봅니다. A29 = A16*A8*A4*A1로 표현할 수 있고, 이는 다시 A24*A23*A22*A20으로 생각할 수 있습니다. 함수 func(num)은 .. 2023. 4. 30.
[BOJ] 10167. 금광 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 www.acmicpc.net 어떤 2차원 그래프에서, 가능한 직사각형 모양의 범위 내부에 있는 정점의 값의 합 중 최댓값을 구하는 문제입니다. 좌표 x, y의 범위는 (0 ≤ x,y ≤ 10^9)인데, 정점의 개수는 최대 3000개이므로 좌표 압축을 사용해 (0 ≤ x,y < 3000) 으로 만들어줍니다. 시간 제한은 3초이므로 O(N^2logN) 으로 해결하면 됩니다. 일반적으로 사각형을 선택하는 기준은 세로 선 두 개, 가로 선 두 개로 O(N^4)라고 생.. 2021. 2. 20.
[BOJ] 16287. Parcel 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 요약하자면, 주어진 배열 A 안의 임의의 4개의 원소들의 합이 W가 되는 경우가 있는지 여부를 출력하는 문제이다. 처음 생각났던 풀이는 앞의 세 원소는 하나씩 고르고 마지막 원소는 lower_bound로 찾기였다. 당연히 세 원소 고르는 것만 O(N^3)이고 N ≤ 5,000인데 될리가 없다. 시간복잡도 O(N^2) 안에 풀어야 하기 때문에 원소들을 두 개씩 묶는다는 아이디어까지는 쉽게 떠올릴 수 있었다. 원소 두 .. 2021. 1. 27.
[BOJ] 13334. 철로 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 처음 생각했던 풀이는 각 (집, 사무실) 쌍을 시작점 기준으로 정렬한 후 각 쌍을 순회하며 뒤쪽의 끝점들만 따로 정렬한 후 upper_bound로 계산하기...였다. 잘 안 풀리는데다 좋은 풀이도 아닌 것 같아서 매주 일요일마다 진행하는 알고리즘 스터디에 가져갔는데, 이거 우선순위 큐 문제라는 얘기를 듣고 바로 풀이가 생각나서 뚝딱뚝딱 풀었다. struct comp_second { bool operator()(p.. 2021. 1. 27.
[BOJ] 6549. 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 www.acmicpc.net 나를 몇달동안 괴롭혔던 문제다. 처음에는 로직이 생각이 안 났고, 로직을 알고 나니 구현이 귀찮았다... 사실 귀찮아할 만큼 구현이 복잡한 문제는 아니고, 아이디어만 알면 쉽게 풀 .. 2020. 5. 13.
[BOJ] 15678. 연세워터파크 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 ≤ Ki ≤ 109) www.acmicpc.net 처음에는 아무 생각 없이 그냥 DP로 짰다가... 시간초과가 났다. 당연히 그렇게 쉬울 리가 없을 거라고는 생각했지만 도저히 로직이 생각이 안 나는걸.. 2주동안 이걸 못 풀고 죽어가고 있었는데 이 사람이 풀어주셨다. O(nlogn) 풀이 | #include using namespace std; #define INF 987654321987654321 int N, D; long long a[100000], .. 2020. 4. 29.
[BOJ] 2098. 외판원 순회 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 현재까지 방문한 경로를 표현할 때 비트마스크를 이용하는 문제이다. 개인적으로 DP 배열을 현재 경로와 인덱스 두 개의 인자를 써야 한다는 아이디어를 떠올리기가 힘들었다. #include #include using namespace std; #define INF 1000000000 int N, W[16][16]; int dp[65536][16]; i.. 2020. 4. 17.

티스토리툴바