BOJ8 6549. 히스토그램에서 가장 큰 직사각형 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 티어 : 플래5 세그먼트 트리로 풀었다. 다른 방법으로도 풀어봐야겠다. #include #include using namespace std; int n, arr[100005], seg[400005]; int init(int index, int left, int right){ if(left == right) return seg[index] =.. 2023. 7. 21. 1086. 박성원 https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 티어 : 플래5 정말 오랜만에 DP문제를 풀어봤다. 꽤 난이도가 있었는데, 적용되는 dp 개념자체는 어렵지 않고, 메모이제이션 해주는 방법이랑 구현 과정이 난이도가 있어 티어가 플래티넘인 것 같다. 메모이제이션 구현 방법이 잘 생각나지 않아 계속 고민하고 있었는데, 비트 방식으로 메모이제이션을 구현하는 아이디어를 얻어 해결할 수 있었다. 문제를 해결할 로직을 구체적으로 정리한 후 본격적으로 코딩을 시작하기 전에 다른 사람의 블로그 글을 .. 2023. 7. 20. 10868. 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 티어 : 골드1 세그먼트 트리로 풀었다. 15분 정도 걸린거 같다. #include #include using namespace std; #define MAX 1000000000; int arr[100005], seg[400005]; int n, m; int init(int index, int left, int right){ if(left == right) re.. 2023. 7. 19. 8980. 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 티어 : 골드1 struct 구조체와 std sort를 활용해 택배가 도착하는 마을의 번호가 작은 배달 순서로, 도착 마을의 번호가 같다면 출발 마을의 번호가 큰 순서대로 정렬하였다. 정렬된 순서대로 배달을 진행하여 답을 구하였다. #include #include using namespace std;; int n, c, m, ans; int box[2005]; typedef s.. 2023. 7. 18. 이전 1 2 다음