MingyuPark

문제 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 아이디어 A에서 B로 가는 Bottom-up 방식보다는 B에서 A로 가는 Top-down 방식이 더 편하다. 왜냐하면, A에서 B로 갈 때는 2를 곱하는 연산, 1을 수의 가장 오른쪽에 추가하는 연산이 모두 가능하기 때문에 모든 조합을 고려하면서 가야한다. (적고 보니 bfs로 가능하려나,, 고민해봐야겠다.) 반대로 B에서 A로 갈 때는 매 step마다 한 가지의 경우밖에 없다. 예제 입력 1을 예로 들어보자. A = 2, B = 162이다. → 1. Bottom up 2 → 4도 가능하고, 2→21도 가능하다. 2..

문제 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 아이디어 투 포인터 기법을 이용하면 된다. 수열의 길이가 최대 10만 개이기 때문에, for loop를 이용해서 하나하나 계산할 경우 최대 10^10번의 계산을 해야 한다. 이 경우 투 포인터 알고리즘을 이용할 수 있다. 문제에 주어진 설명을 빌려서 말하자면 양 끝에서 포인터를 좁혀가면서 조건에 맞는 모든 경우를 찾는 문제이다. 하지만 ..

문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 아이디어 진실을 아는 사람들의 번호를 n_know_lst 라는 리스트에 저장한다. 이 때, 처음에는 진실을 아는 사람이라고 했지만, 다른 말로 하면 거짓말을 칠 수 없는 사람들이기도 하다. 왜 이렇게 표현했냐면, n_know_lst에 속하는 사람과 같은 파티에 있었던 사람에게는 거짓말을 칠 수 없게 되는 것이다. 즉, 모든 파티를 순회하면서 n_know_lst 의 정보를 이용해서, n_know_lst에..

문제 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 아이디어1 - DP Pypy3에서는 성공했고, Python에서는 시간 초과가 발생한 방법이다. 아이디어는 다음과 같다. 자연수 n에 대하여, n을 최소 개수의 제곱수 합으로 표현했을 때 그 개수를 f(n)이라고 하자. 이 때, n보다 작은 모든 제곱수 k에 대해 m = n - k 라고 하면, f(n)은 f(m)의 최솟값 + 1이 된다. (제곱수를 더한다는 ..

문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 아이디어 그리디 알고리즘으로 접근할 수 있다. 그 근거를 살펴보자. 지금 시점에 시작할 수 있는 회의들 중에서 가장 빨리 끝나는 회의를 진행하면 된다. 시작 시간을 고려하면 안된다. 시작 시간 자체는 다음 회의를 탐색하는 데에 있어서 기준이 될 수 없다. 이번 회의가 일찍 끝나면 끝날수록 더 많은 다음 회의를 고려할 수 있다. 결론은, 일단 모르겠고 제일 먼저 끝나는 걸 찾자. 이다. 예를 들어보자. 회의 시간이 (1, 4), (2, 3), (3, 5) 라고 하자. 시작 시간 기준으로 정렬하면 (1, 4) ..

문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 아이디어 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) - 위의 조건 때문에 Ai번째 동전의 액수는 Ai-1번째 동전으로 만들 수 있게 된다. 즉 모든 상황에서 가장 비싼 금액의 동전을 사용하는 것이 가장 최적의 선택이 된다. - 따라서, 이 문제는 그리디 알고리즘으로 접근할 수..