분류 전체보기 (89) 썸네일형 리스트형 2024-03-07 -선 긋기(2170, 백준) 간단한 그리디 문제였다. 한선분이 다른 선분의 시작점을 포함하고(겹치고)있다면, 두 선분을 하나의 선분으로 합쳐서 보면 된다. 시작점을 기준으로 정렬을 한 뒤, 앞에서부터 탐색해나간다. 선분의 시작이Si, 끝점이 Ei라면, Si가 현재 이어지고있는 선분안에 포함되며, Ei가 그 선분의 끝점보다길면 갱신해주고 아니라면 ans에 선분의 길이를 더해준다. 더보기 #include #include #include using namespace std; int n; int ans; vector vec; int main() { int i, j; scanf("%d", &n); for(i=0;i n) pq.pop(); } } printf("%d", -pq.top()); return 0; } -.. 2024-03-06 -작업(2056, 백준) ACM craft라는 문제와 똑같다. 순서가 정해져있기에 위상정렬을 떠올릴 수 있다. 기초적인 위상 정렬 문제이다. 위상 정렬에서 진입차수를 제거해갈 때, 해당 노드의 값을 갱신 시켜준다. (선행 노드가 걸리는 시간중 가장 최대 시간이 지난 후, 작업이 가능하다는 점을 생각해보자) 더보기 #include #include #include #include using namespace std; int time[10010], ans[10010], ent[10010]; vector vec[10010]; int n; int main() { int i, j; scanf("%d", &n); for (i = 1; i 백준(Baekjoon)문제 풀이 - 3665 최종 순위(C++) 최종 순위 문제 https://www.acmicpc.net/problem/3665 원래 등수와 서로 바뀐 등수가 출력 되었을 때의 새로운 등수를 출력하는 문제이다. 만약 확실하지않다면 "?" , 데이터의 일관성이 없어 오류가 발생하는 경우에는 "IMPOSSIBLE"을 출력한다. 입출력 형식 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500) n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다. 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000) 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이.. 백준(Baekjoon)문제 풀이 - 10800 컬러볼(C++) 컬러볼 문제 https://www.acmicpc.net/problem/10800 같은 색의 공끼리는 먹을 수 없고, 자기보다 크기가 작은 공끼리만 먹을 수 있을 때, 주어진 공이 공을 얼마나 먹을 수 있는지, 먹을 수 있는 공의 총 합을 출력하면 되는 문제이다. 입출력 형식 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다. N개의 줄을 출력한다. N개의 줄 중 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.. 2024-03-05 -쇠 막대기(10799, 백준) 기본적인 STL stack자료구조 응용 문제이다. '('이 들어올때는 stack에 push해주고, ')'이 들어오면 한 막대기가 완전히 잘린 것임으로 ans++을 해준다. 하지만 '('와 ')'가 연속해서 들어오는 경우 즉, 레이저가 들어오게되면, 현재범위에 있는 모든 막대기를 잘라야함으로, stack의 크기만큼 ans에 더해준다. 더보기 #include #include #include using namespace std; int l; char s[100010]; stack st; int main() { int i, j; scanf("%s", s); l = strlen(s); for (i = 0; i < l - 1; i++) { if (s[i] == '(' && s[i +.. 2024-03-04 -카드게임(10801, 백준) 구현 문제이다. 10개의 수가 들어간 배열을 2개 입력받고 비교하며, 더 큰수가 있는 쪽의 cnt값을증가시킨다. 그후, cnt가 더 큰쪽을 출력한다. cnt가 서로 같다면, D를 출력한다. 더보기 #include int a[15], b[15]; int a_win = 0, b_win = 0; int last_win = -1; // 1 = a, b = 2; int main() { int i; for(i=0;i 백준(Baekjoon)문제 풀이 - 1300 K번째 수(C++) K번째 수문제 N*N배열 A를 오름차순으로 나열했을때 k번째수를 구하는 문제이다.입출력 형식첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. B[k]를 출력한다. 37 6아이디어 N범위가 10^5임으로, 배열을 구해 정렬하려면 O(N^2)즉, 시간초과가 난다. 따라서, 배열을 직접 구하는 대신에 다른 방법을 사용해야 한다. 이러한 방법을 생각해보자. 우선 문제에서 말하는 답을 ans라고 두었을때, 배열에서 ans보다 작거나 같은 수가 k개있을때, ans는 정답이 될 수 있다. 즉, ans보다 작거나 같은수가 k개임을 만족하는 ans의 값을 찾는 것이 이 문제의 핵심이라는 뜻이다. 그렇다면.. 백준(Baekjoon)문제 풀이 - 19542 전단지 돌리기(C++) 전단지 돌리기 문제 https://www.acmicpc.net/problem/19542 주어진 트리모양의 길 위에 전단지를 돌리는 문제이다. 힘을 나타내는 D보다 작은거리는 탐색하지 않고, 생각했을때의 최소 경로를 구해야되는 문제이다. 입출력 형식 첫째줄 노드의 수(1 이전 1 ··· 6 7 8 9 10 11 12 다음
