전체 글140 [백준] 13904 - 과제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net N개의 과제의 마감일과 점수가 주어졌을 때, 얻을 수 있는 과제 점수의 최댓값을 구하는 문제이다. 이 문제는 우선순위 큐를 이용하는 방법과 이용하지 않는 방법 두 가지로 풀 수 있다. 먼저 우선순위 큐를 이용하는 방법이다. 입력으로부터 마감일이 가장 긴 날을 구한다. 입력을 마감일 오름차순으로 정렬한다. 1로부터 구한 최대 마감일부터 하루씩 줄여가며 우선순위 큐에 해당 날에 풀 수 있는 문제들을 모두 집어넣는다. 매 날마다 우선순위 큐의 t.. 2022. 7. 19. [백준] 11003 - 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 처음에 이 문제의 시간과 N 범위를 보고 세그먼트 트리를 생각하여 제출했는데 TLE를 받았다. 세그먼트 트리 생성 시간 NlogN + 쿼리시간NlogN 해서 약 2억 2천 번의 연산으로 될 줄 알았는데 아니었고, 입출력 최적화 및 이것저것 해보았는데도 되지 않길래 다른 방법으로 AC를 받았다. 문제를 간단하게 표현하자면 이렇다. [max(1, i - L + 1), .. 2022. 7. 14. [백준] 4196 - 도미노 https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net SCC를 연습하고 있던 중에 발견한 흥미로운 문제이다. 도미노의 특성상 하나의 도미노를 쓰러트리면 다른 도미노도 쓰러질 수 있기 때문에 SCC를 찾아야 한다. 그런데 여기서 끝나는 것이 아니다. 바로 하나의 SCC는 다른 SCC에 영향을 줄 수 있다. 만약 1 -> 2, 2 -> 3, 3 -> 1, 4 -> 3, 5 -> 4 같은 경우에서 SCC는 {1, 2, 3}, {4}, {5}이지만 5번 도미노 하나만 쓰러.. 2022. 7. 14. [백준]1525 - 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 흥미로운 문제였다. 2차원 배열 형태의 격자를 1차원 형태의 문자열처럼 만들고, map 자료구조를 이용해서 방문 체크를 할 수 있다. 원래는 빈 칸 주위의 숫자들을 빈칸으로 이동하면서 퍼즐을 맞추지만, 조금 더 편리하게 구현하기 위해 빈칸이 이동하는 것으로 생각해서 dx, dy 기법을 편리하게 이용할 수 있었다. #include #include #include using namespace std; map m; int main() { string s = ""; for (int.. 2022. 7. 13. [백준]1766 - 문제집 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 처음에 단순히 위상 정렬만 사용하면 되는데 왜 골드 2나 레이팅 돼 있는 건가 생각해서 조금 당황했지만, 가능하면 쉬운 문제부터 풀어야 한다. 이 문장 하나 때문인 것 같다. 위상 정렬의 결과로 순서를 매길 수 없는 문제들이라면, 우선순위 큐를 이용해서 무조건 작은 문제들이 먼저 풀리게끔 만들어 주면 된다. #include #include #include #inclu.. 2022. 7. 13. 이전 1 ··· 13 14 15 16 다음