전체 글
-
[BOJ 15906, Python 3] 변신 이동 게임알고리즘/BOJ 2021. 9. 8. 15:07
https://www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 풀이 처음엔 BFS를 생각해볼 수 있는데 일반 이동은 (이동 횟수) + 1이지만, 변신모드로 변할 때는 (이동 횟수) + t가 되기 때문에 이걸 단순 큐에 넣어서 풀어보면 이미 방문한 경로가 다시 업데이트될 수도 있기 때문에 시간이 오래 걸리므로 다익스트라 알고리즘을 생각해볼 수 있습니다. 방문 방법은 visit 배열 2개로 나눠 각각 변신모..
-
[BOJ 22984, Python 3] 반짝반짝 2알고리즘/BOJ 2021. 9. 6. 11:43
https://www.acmicpc.net/problem/22984 22984번: 반짝반짝 2 국렬이는 지난 겨울에 수현이가 크리스마스 트리를 장식하고 남은 전구 스트립을 훔쳐서 자신의 방을 장식하려고 한다. 전구 스트립에는 전구 $N$개가 일(一)자로 설치되어 있다. 전구들은 전원 www.acmicpc.net 알고리즘학회에서 gojib2002님의 풀이를 들었음 풀이 일단 일반 전구가 켜질 확률을 p[i]라고 둘 때, p[i] 확률로 불이 들어오는 i번째 전구의 기댓값은 p[i]인 것을 알 수 있습니다. 전구가 켜진다면 1개가 켜지고, 켜질 확률이 p[i]이므로 1 * p[i] = p[i]인 것입니다. 그래서 일반 전구가 켜지는 모든 기댓값은 p[1] + p[2] + p[3] + .... + p[n]입니..
-
[BOJ 11689, Python 3] GCD(n, k) = 1알고리즘/BOJ 2021. 9. 6. 11:35
https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 GCD(n, k) = 1을 만족하는 자연수란 n과 k가 서로소 관계에 있다는 뜻입니다. 그래서 1부터 n사이에 n과 서로소인 개수를 구하는 공식은 오일러 피 함수가 있으므로 이 공식을 이용하여 개수를 찾아주면 되는 문제입니다. 자세한 설명은 https://ohgym.tistory.com/14 나 https://blog.chodaeho.com/posts/2021/eulers-totient-function/ 블로그를 참조하면 됩니다. 코드 1..
-
[BOJ 22988, Python 3] 재활용 캠페인알고리즘/BOJ 2021. 9. 4. 23:01
https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 풀이 X ml인 헤어 에센스를 최대한 많이 만들어야 하므로 일단 2개로 1개를 만드는 것을 생각할 수 있습니다. 이러면 투포인터를 사용해 a = 0, b = len(C) - 1로 설정하여 C[a] + C[b] >= 0.5 * X가 되면 답에 1을 추가해줍니다. 그리디적인 아이디어인데 [남은 용량이 제일 작은..
-
[BOJ 22981, Python 3] 휴먼 파이프라인알고리즘/BOJ 2021. 9. 4. 23:00
https://www.acmicpc.net/problem/22981 22981번: 휴먼 파이프라인 모든 상자를 최대한 빠르게 옮기는 경우의 작업 시간을 분 단위로 출력한다. www.acmicpc.net 풀이 문제를 읽어보면 제일 느린 사람의 속도로 맞추기 때문에 v를 정렬하면 팀 한 개는 속도가 v[0]으로 확정되어 있습니다. 그리고 i != 0인 다른 속도 v[i]를 나머지 팀의 속도로 정해둔다고 가정하면 최대한 빠르게 옮기는 경우는 v[i]보다 속도가 빠른 n - i명의 사람들을 전부 v[i]가 속한 팀에 들어가는 것입니다. v[0]
-
[BOJ 13334, Python 3] 철로알고리즘/BOJ 2021. 9. 3. 16:50
https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 풀이 일단 문제를 풀려면 정렬을 해야한다는 것을 아실 수 있는데, 그리디 알고리즘 문제를 좀 푸셨다면 큰 값을 기준으로 오름차순 정렬해야 한다는 것을 알 수 있습니다. 이런 아이디어를 사용하는 그리디 문제에서 가장 기초적인 문제는 이 문제(풀이)가 있습니다. 문제에서 구하는 것은 좀 다르지만 아이디어는 비슷하죠 이렇게 정렬을 한 뒤엔 이제 철로의..
-
[BOJ 10989, Python 3] 수 정렬하기 3알고리즘/BOJ 2021. 9. 3. 16:42
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 메모리 제한이 많이 작습니다. 그런데 정렬할 수의 최댓값이 10,000이므로 크기가 10001인 배열을 만들고, 어떤 수 x가 있으면 arr[x] += 1을 해주어서 마지막에 출력할 때는 배열의 인덱스를 해당 위치의 리스트가 가지고 있는 값만큼 출력을 해주면 됩니다. 이런 정렬은 카운팅 소트(Counting sort)라고 부르며 자세한 내용은 https://00ad-8e71-00ff-055d.tistory.co..
-
[BOJ 4619, Python 3] 루트알고리즘/BOJ 2021. 9. 3. 16:35
https://www.acmicpc.net/problem/4619 4619번: 루트 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, B와 N이 주어진다. (1 ≤ B ≤ 1,000,000, 1 ≤ N ≤ 9) 입력의 마지막 줄에는 0이 2개 주어진다. www.acmicpc.net 풀이 B의 값도 작고, N의 값도 작아서 바로 브루트포스를 생각할 수 있습니다. 계산을 더 빠르게 하기 위하여 N = 1일 때는 B = A가 성립하므로 이 경우를 제외하고, N = 2일 때 B = 1,000,000인 경우는 A = 1,000이므로 N = 2이상부터는 1부터 1,000까지 브루트 포스를 통하여 확인해주시면 됩니다. 코드 1 2 3 4 5 6 7 8 9 while 1: b, ..