[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] 6549. 히스토그램에서 가장 큰 직사각형
6549번: 히스토그램에서 가장 큰 직사각형 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 www.acmicpc.net 나를 몇달동안 괴롭혔던 문제다. 처음에는 로직이 생각이 안 났고, 로직을 알고 나니 구현이 귀찮았다... 사실 귀찮아할 만큼 구현이 복잡한 문제는 아니고, 아이디어만 알면 쉽게 풀 ..
2020. 5. 13.
tokki
