개발자 퉁이리

www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 정렬 ⊙ 문제 접근 과정 나무가 걸리는 시간을 입력받고 역으로 정렬시킨다. 날이 지나간 만큼 그 값을 더하고 가장 큰 값을 채택한다. ⊙ 문제 풀이 #include #include #include using namespace std; int N; vector v; int main() { cin >> N; fo..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 그리디 알고리즘 우선순위 큐 ⊙ 문제 접근 과정 결론부터 말하면 가장 작은 두 값을 더하고 두 장 모두에 덮어쓴 값이 최솟값이다. 4 2 3 1, 총 4장의 카드가 있다. 우선 크기 순으로 정렬해보자. 1 2 3 4 덮어썼을 때 가장 적게 값이 증가해야 한다. 그러려면 두 값 모두 작아야 ..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 정렬 ⊙ 문제 접근 과정 진짜 엄청 많이 틀리고 맞췄다... 단순히 정렬하고 높은 수끼리 곱하고 음수는 음수끼리 곱하면 될 줄 알았던 내 과오였다. 문제에 예외 케이스가 생각보다 다양하게 존재한다. 첫 번째로 누구나 생각할 수 있는 음수 X 음수 조합 음수 X 음수 = 양수로 최댓값을 극대화할 수 있다. 두 번째로 0과..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 정렬 ⊙ 문제 접근 과정 vector를 이용해 값을 입력받고 정렬을 해주었다. 그 후 temp 변수를 만들어 현재 위치와 다음 위치의 차이를 계속해서 빼주었다. (테이프가 소모되는 값) 만약 테이프가 남아있으면 계속 반복, 부족하면 count up 후 temp 초기화 후 반복. ⊙ 문제 풀이 #includ..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 정렬 ⊙ 문제 접근 과정 만약 이 문제가 안 풀린다면, 문제 자체가 이해가 안 될 확률이 높다고 생각한다. 서류 순위 면접 순위 1 4 2 3 3 2 4 1 5 5 먼저 서류 순위로 정렬한다. 서류가 1등인 사람의 면접 순위는 4등이다. 그다음 서류 2등과 비교! 만약 서류 2등의 면접 순위가 4등보..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 그리디 알고리즘 정렬 물리학 ⊙ 문제 접근 과정 내림차순 정렬을 한 후, min_element 함수를 사용하여 처음엔 시간 초과가 났다. 곰곰이 생각해보니 정렬을 했는데 min_element를 사용할 이유가 없었다. 바로 index로 접근하여 max함수를 이용해 정답 값인 rope를 구하였다. ⊙ 문제 풀이 #include..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 정렬 ⊙ 문제 접근 과정 벡터로 값을 받고 정렬한 후 두 번째 값과 첫 번째 값을 비교해주면서 count 값을 올려주었다. ⊙ 문제 풀이 #include #include #include using namespace std; int N; int cnt=1; vector v; bool comp(pair a,pair b) { if(a.second == b.second) { return a.first < b.first; } else { retu..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 정렬 두 포인터 ⊙ 문제 접근 과정 투 포인터 문제다. start index 변수와 end index 변수를 만들어주고 index 값을 올리고 줄이면서 result 값을 찾아주면 된다. n값 입력받고 vector에 n의 개수만큼 값 넣기 찾아야 할 x값 입력받기 vecto..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 정렬 두 포인터 ⊙ 문제 접근 과정 문제에서 KeyPoint를 찾았는가? KeyPoint: 정렬되어 있는 정렬이 이미 되어있다. 그렇다면 인덱스만을 이용하여 문제를 풀 수 있지 않을까? 처음에는 "정렬되어 있는"을 무시하고 문제를 풀었는데 시간 초과가 떴다. #include #include #inclu..

www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 정렬 ⊙ 문제 접근 과정 그리디 알고리즘이다. 그리디 알고리즘은 배열을 하면 손쉽게 풀 수 있다. 값을 입력받고 오름차순으로 정리한 뒤에 순서대로 result 변수에 값을 넣어주고 값을 도출해냈다. ⊙ 문제 풀이 #include #include #include using namespace std; int main() { vector vec; int N; int to..