크롱의 Dev Log

문제 링크: www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 한번에 짠 아래 코드. 테스트케이스는 문제 없이 동작했는데 채점 돌리니까 7%에서 시간 초과 났다. 고민하다가 결국 우선순위 큐 써서 해결했다. #include #include #include #define MAX 300000 using namespace std; long long ans = 0; int n, k; pair jewelry[..

문제 링크: www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 문제 설명: 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 문제 접근 방법: N은 1000이하의 자연수이므로 init()함수를 통해 1~1000까지 한수인지 아닌지를 배열 hansoo에 저장해뒀다. ha..

문제 링크: www.acmicpc.net/problem/1003 피보나치 함수를 구현하는 여러 방법이(재귀 함수 등)있지만 기존의 값을 저장하지 않고 새로운 숫자의 피보나치 값을 구하려면 이전 값까지 계속 다시 연산해야 한다. 예를 들어, 새롭게 숫자 5의 피보나치 결과를 구하려면 이전에 피보나치 4, 3, 2, 1을 구했더라도 새롭게 다시 연산해야 한다. 다른 숫자에 대해서도 기존에 연산한 결과를 활용하지 못하고 새롭게 연산해야하므로 답은 제대로 나오겠지만 시간이 많이 걸리게 된다. 이 문제는 제한시간이 0.25초로 위 방법을 사용하면 시간 초과가 뜬다. 그럼 어떻게 시간 초과를 피할 수 있을까? 답은 다이나믹 프로그래밍(동적 계획법)이다. 다이나믹 프로그래밍(동적 계획법)이란? 기존의 연산 결과를 저..

문제 링크: https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si b; } }; // 강의 끝나는 시간 저장(빨리 끝날 수록 우선순위 높음) // pq 원소 값 : 해당 인덱스의 강의실에서 가..

문제 링크: https://www.acmicpc.net/problem/10411041번: 주사위첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수www.acmicpc.net 주사위로 N*N*N크기의 정육면체를 만들었을 때 3면이 보이는 주사위, 2면이 보이는 주사위, 1면이 보이는 주사위의 개수를 구해서 각 개수를 3면이 보였을 때 최소 조합, 2면이 보였을 때 최소 조합, 주사위의 적힌 최소 숫자(1면이 보였을 때 최소 조합)에 곱해주면 된다.즉 (3면 최소조합)*(3면 보이는 주사위 개수) + (2면 최소조합)*(2면 보이는 주사위 ..