https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 이 문제는 그리디 알고리즘을 활용해면 해결할 수 있다. 문제 접근 시 주사위가 보이는 면만 계산하면 된다. 이유는 최소 값을 구하기 때문에 A, B, C, D, E, F 의 값중 가장 작은 값 3개를 뽑고 3개면이 보이는 경우, 2개면이 보이는 경우, 1개면이 보이는 경우를 계산하면 된다. N = 1인 경우는 작은 면 순서대로 5개의 면만 더하면 된다. N = 2 이상부터는..
분류 전체보기
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 매우 어려웠다. 다른 사람들의 코드를 보고 풀었다. 트리의 순회에 대해 자세히 알아야 할 것 같다. #include #include #include using namespace std; int N; vector graph[10001]; int visited[10001]= { 0, }; int result = 0; int endPoint = 0; void dfs(int node,..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 이 문제는 그리디 알고리즘을 통해 해결할 수 있다. 입력은 벡터를 사용해서 S와 T를 pair형태로 삽입한다. 그 후 우선순위 큐를 greater로 정렬하고, vector의 두번째 값인 T를 큐에 삽입한다. 큐에 모든 vector의 second 값을 삽입하는데 이때 가장 작은 값이 현재 벡터의 S값보다 작거나 같으면 큐에서 값을 뺀다. #include #include #include #include using namespace std; int ..
https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 이 문제는 그리디 알고리즘을 활용해서 해결할 수 있다. 센서들 값을 입력받고 배열을 정렬한다. 센서들의 값이 정렬되었으므로 센서들의 차이를 통해 거리를 계산하고 배열에 삽입한다. 그후 거리 배열을 K-1만큼 pop한 후 배열의 크기를 출력한다. #include #include #include using namespace std; int N,K; bool sorter(int..
https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. DP를 통해 누적합을 계산한다. i와 j사이의 누적합은 DP[j] - DP[i-1] 값이 된다. 즉, 1 2 3 4 5 6 7 8 9 에서 3과 8 사이의 값은 (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) - (1 + 2) = (3 + 4 + 5 + 6 + 7 + 8) 이된다. #include using namespace..
https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. DP를 통해 누적합을 계산하고 출력할 변수에 누적합을 누적하면 된다. #include #include #include using namespace std; int N; int dp[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; vector v; for (int i = 0; ..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이 문제는 그리디 알고리즘을 활용해야한다. 회의의 시작 시간과 다음 회의의 끝나는 시간을 비교하여 시작 시간이 작거나 같으면 선택 가능한 회의 수를 증가시킨다. 그 다음 순회를 위한 시작 시간을 선택된 회의의 시작 시간으로 변경한다. #include #include #include using namespace std; int N; int dp[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; vector..
https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 이 문제는 우선순위 큐를 사용하면 해결할 수 있다. 삽입할 수가 0이면 큐에서 빼서 출력하고 아니면 삽입하면 최소 힙을 구현할 수 있다. #include #include #include #include using namespace std; int N; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)..
