분류 전체보기
-
[Python 3] BOJ - 2536 "버스 갈아타기"BOJ 2021. 8. 17. 18:57
# 문제 링크 https://www.acmicpc.net/problem/2536 2536번: 버스 갈아타기 첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다 (1 ≤ m,n ≤ 100,000). 두 번째 줄에 버스의 수 k (1 ≤ k ≤ 5,000)가 주어진다. 세 번째 줄부터 k 줄에 걸쳐 각 줄에 버스의 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그래프 모델링이라고 생각한다. n과 m에 비해 k가 5000으로 굉장히 작고, 문제에서 버스가 지나지 않는 곳에 출발점이 없기 때문에 다시 말해 버스까지 걸어갈 일이 없기 때문에 k만으로 문제를 풀 수 있다. 위 그림은 예제 입력 1의 상태를 나타낸 것이다. 그런데 사실 그림 1에서 버스 1과 8은 생략되..
-
[Python 3] BOJ - 10800 "컬러볼"BOJ 2021. 8. 16. 22:49
# 문제 링크 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 누적 합과 lower_bound, 좌표 압축의 적절한 이용이라고 생각한다. 현재 계산해야 하는 공의 색깔이 a이고 무게는 b라고 하자. 이 때, 전체 무게에서 b 이상인 공은 잡을 수 없다. 또한 b 미만이라 하더라도 a색깔인 공도 잡을 수 없기에 전체 무게에서 무게 b 이상의 공의 총 무게와 a 색깔에서 무게 b 미..
-
[Python 3] BOJ - 1799 "비숍"BOJ 2021. 8. 13. 21:34
# 문제 링크 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 비숍의 특징을 이용한 백트래킹이다. 비숍의 특징은 체스판을 벗어나지 않는 한 대각선으로 원하는 만큼 이동할 수 있다는 것이다. 문제에서 체스판의 최대 길이는 10이고 정사각형이므로 극단적으로 모든 칸이 비숍을 놓을 수 있는 1이라면 $$2^100$$이기 때문에 시간 초과를 피할 수 없어 보인다. 그러나, 비숍을 특징에 따라 모든 방향의 대각선을 검사한다면..
-
[Python 3] BOJ - 3078 "좋은 친구"BOJ 2021. 8. 12. 16:20
# 문제 링크 https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 upper bound의 활용이라고 생각한다. 문제에서 제시한 좋은 친구의 조건은 점수의 차이가 K이하이면서 같은 이름을 갖는 친구이다. 따라서 우선적으로 이름이 같은 사람끼리 성적을 비교해야 한다. 따라서, 이름의 길이를 key, 그 이름의 길이를 갖는 사람의 성적 리스트를 value로 갖는 dictionary가 필요하다. 이..
-
[Python 3] BOJ - 2812 "크게 만들기"BOJ 2021. 8. 11. 17:16
# 문제 링크 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘과 스택이라고 생각한다. 문제를 풀기 전에 간단한 다른 문제를 풀어보자. 0이상 9이하의 어떤 n개의 수가 주어지고, n개의 수를 모두 사용하여 n자리 숫자를 만들때 가장 크게 만드는 방법은 무엇인가? 당연히 큰 수부터 채워나가는 것이다. 따라서, 우리는 n개가 아니라 n-k개를 이용하는 것이지 문제의 큰 틀은 바뀌지 않았음을 알 수 있다. 그런데 아무렇게 k개를 제외하면 정답을 구할 수 없다. 그런데 우리는..
-
[Python 3] BOJ - 2878 "캔디캔디"BOJ 2021. 8. 10. 18:34
# 문제 링크 https://www.acmicpc.net/problem/2878 2878번: 캔디캔디 첫째 줄에 M(1 ≤ M ≤ 2×109)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×109보다 작으며, 친구들이 받고 싶어하는 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 이분 탐색이라고 생각한다. 여러 포스팅에서 보았듯이, 이분 탐색의 핵심은 특정 x에 대한 대답이 YES일 때, x+1, x+2, ... 에 대한 대답도 YES가 되는지를 파악하는 것이다. 그래야 반씩 줄여서 탐색하는 것이 의미가 있기 때문이다 따라서 우리가 최소화 하고 싶은 것은 각 불만의 제곱의 합이다. 그런데 그냥..
-
[Python 3] BOJ - 14476 "최대공약수 하나 빼기"BOJ 2021. 8. 9. 16:47
# 문제 링크 https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 prefix sum과 suffix sum이라고 생각한다. 물론 세그먼트 트리를 사용해도 무방하지만, 더 간단하게 풀 수 있다. 현재 k번째 수를 제외하게 되면 남는 구간이 [0, k - 1]과 [k + 1, n - 1]이다. 그런데 gcd연산은 결합법칙이 성립하므로 즉, gcd(a,b,c) = gcd(gcd(a, b), c)이므로 누적합과 같이 볼 수 있다..
-
[Python 3] BOJ - 9007 "카누 선수"BOJ 2021. 8. 6. 17:03
# 문제 링크 https://www.acmicpc.net/problem/9007 9007번: 카누 선수 이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 투 포인터라고 생각한다. 왜냐하면 n의 제한이 1000이기 때문에 두 반의 모든 몸무게의 조합을 비교하게 되면 \(1000^2\)만큼 시간이 걸리기 때문이다. 따라서 리스트가 2개가 되고 다시 두 반의 조합을 brute-force하게 구하게 되면 \(1000 ^ 4\)이 걸리기 때문에 시간 초과를 피할 수 없다. 위 그림 1..