알고리즘
-
[BOJ 19939, Python 3] 박 터뜨리기알고리즘/BOJ 2021. 7. 30. 18:33
https://www.acmicpc.net/problem/19939 19939번: 박 터뜨리기 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 www.acmicpc.net 풀이 같은 문제: https://www.acmicpc.net/problem/1789 1789 문제랑 풀이 방식이 똑같습니다. 각 바구니에 담긴 공의 개수가 서로 달라야하니 1개, 2개, 3개, ... 이렇게 넣어줍니다. 이랬는데 비어있는 바구니를 발견하면 -1을 출력하고, 그게 아니라면 공을 다 사용하거나 몇 개가 남았을 겁니다. 여기서 이제 몫과 나머지를 이용하여 문제를 풀면 됩니다. ..
-
[BOJ 16435, Python 3] 스네이크 버드알고리즘/BOJ 2021. 7. 30. 17:57
https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 풀이 오름차순으로 정렬하여 한 개씩 먹다가 못 먹는 게 있으면 출력하고 종료한다. 끝까지 다 먹었으면 l + n을 해준다. 코드 1 2 3 4 5 6 n, l = map(int, input().split()) h = sorted([*map(int, input().split())]) for i in range(n): if l + i
-
[BOJ 1086, C++] 박성원알고리즘/BOJ 2021. 7. 29. 22:42
https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 풀이 먼저 간단하게 생각해보면 DP 함수 인자에 문자열을 들고 다니는 것을 생각해볼 수 있지만 이렇게 하면 시간 초과가 나올겁니다. 아니면 메모이제이션 배열에 문자열을 넣을 수도 있는데, 이건 돌아갈 것 같지만 마지막에 큰 수를 나머지 연산을 이용해서 풀어야 하는 것이라 매우 귀찮은 작업이 될 수 있습니다. 그래서 문자열 대신 숫자로 넣어봄직을 생각해볼 수 있는데, 여기서 정수론 개념이 들어갑니다. 예제 문제로 {5221,40,1,58,..
-
[BOJ 1028, C++] 다이아몬드 광산알고리즘/BOJ 2021. 7. 29. 22:29
https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 풀이 문제 풀이 아이디어는 의외로 쉽습니다. 위, 아래, 오른쪽, 왼쪽 꼭지점이 있는데, 여기서 오른쪽 꼭지점에서 ↗로 갈 수 있는 최대 길이, ↘로 갈 수 있는 최대 길이를 구해주고, 왼쪽 꼭지점에서 ↖로 갈 수 있는 최대 길이, ↙로 갈 수 있는 최대 길이를 구해주면 됩니다. 그래서 총 4개의 배열이 필요하고 이것을 전부 DP로 구해주면 됩니다. 이제 다이아몬드의 최대 크기를 구하는데, 이때 풀이는 2가지로 나뉩니다. 하나는 2중 for문을..
-
[BOJ 3056, C++] 007알고리즘/BOJ 2021. 7. 29. 22:22
https://www.acmicpc.net/problem/3056 3056번: 007 비밀 요원 007은 제임스 본드로 유명한 비밀 요원이다. 최근 알려진 정보에 의하면 제임스본드는 대다수 미션을 자신이 직접 수행하지 않는다고 한다. 본드는 미션을 자신과 비슷하게 생긴 사촌 www.acmicpc.net 풀이 N의 제한이 작으니 비트마스크를 이용해야 한다는 생각을 할 수 있습니다. 주의할 점은 계속 소수점이 나와야하기 때문에 double을 계속 사용하여 int형이 절대 나오지 않도록 주의해주면 됩니다. 정답률이 의외로 낮던데 아마 여기에서 많이 틀렸을 거라고 생각합니다. 문제에서 미션 성공률이 제일 높은 확률을 구하라고 했으므로 max를 이용하는 top-down 코드를 짜면 됩니다. DP말고도 헝가리안 메..
-
[BOJ 15904, Python 3] UCPC는 무엇의 약자일까?알고리즘/BOJ 2021. 7. 29. 22:09
https://www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 풀이 for문을 돌리면서 U -> C -> P -> C가 가능하면 love를 출력하고, 불가능하면 hate를 출력한다. 코드 1 2 3 4 5 6 7 8 s = input() ans = 0 for i in range(len(s)): if s[i] == 'U' and ans == 0: ans += 1 if s[i] == 'C' and (ans == 1 or ans == 3):..
-
[BOJ 14469, Python 3] 소가 길을 건너간 이유 3알고리즘/BOJ 2021. 7. 29. 22:06
https://www.acmicpc.net/problem/14469 14469번: 소가 길을 건너간 이유 3 이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다. 농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거의 없 www.acmicpc.net 풀이 제일 빨리 온 소부터 처리를 한다. 검문 받는 시간은 어떻게 정렬하든 상관이 없다. 코드 1 2 3 4 5 6 7 8 9 n = int(input()) arr = sorted([[*map(int, input().split())] for _ in range(n)]) time = 0 for i in range(n): x, y = arr[i] if time
-
[BOJ 9237, Python 3] 이장님 초대알고리즘/BOJ 2021. 7. 29. 22:04
https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 풀이 내림차순으로 정렬하여 다 자라나는데 오래 걸리는 나무부터 심는다. 코드 1 2 3 4 5 6 7 n = int(input()) arr = sorted([*map(int, input().split())], reverse=True) ans = 1 for i in range(n): ans = max(ans, arr[i] + i + 2) print(ans) Colored ..