BOJ
-
[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..
-
[Python 3] BOJ - 2539 "모자이크"BOJ 2021. 8. 5. 18:34
# 문제 링크 https://www.acmicpc.net/problem/2539 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net # 풀이 개인적으로 생각했을 때 이 문제의 핵심은 이분탐색이라고 생각한다. 왜냐하면 문제의 조건에 맞게 Xcm로 모든 칸들을 덮을 수 있다고 하자. 그렇다면, (X+ 1)cm로 모든 칸들을 덮을 수 있는가? 그렇다. 그렇다면, (X + 2)cm로 모든 칸들을 덮을 수 있는가? 그렇다. 반대로, 문제의 조건에 맞게 Xcm로 모든 칸들을 덮을 수 없다고 하자. 그렇다면, (X - 1)cm로 모든..
-
[Python 3] BOJ - 14863 "서울에서 경산까지"BOJ 2021. 8. 4. 16:18
# 문제 링크 https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net # 풀이 개인적으로 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 주어진 문제에서 시간을 무게라고 생각하면 냅색문제와 완전히 동일한 문제가 된다. 따라서 상태 공간은 현재 idx번째 경로에서 남은 시간이 total일 때, 얻을 수 있는 최대 모금액이며 dp[idx][total]가 된다 그런데 시간이 음수가 될 수는 없으므로 만일 현재 시간..