분류 전체보기
-
[Python 3] BOJ - 1149 "RGB 거리"BOJ 2020. 3. 11. 22:18
# 문제 링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net # 풀이 : 그리디 알고리즘으로 자칫 접급할 수 있지만, 반례를 쉽게 찾을 수 있다. 따라서 이 문제는 그리디 알고리즘으로는 최적해를 찾을 수 없다. 따라서 다이나믹 프로그래밍으로 접근해야 한다. 개인적으로 문제의 핵심은 비록 처음과 끝이 아닌 경우에는 양 옆집과 다른색이 되어야 하지만, 결론적으로 바로 앞집에 의해서만 해당 집의 색깔이 결..
-
[Python 3] BOJ - 1018 "체스판 다시 칠하기"BOJ 2020. 3. 10. 22:54
# 문제 링크 : https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net # 풀이 : 물론 각 칸의 경우에 대해 조사하는 것도 방법이지만 개인적으로는 애초에 검은색으로 시작하는 체스판과 흰색으로 시작하는 체스판, 즉 정답인 케이스 두가지를 미리 만들어 놓고 범위에 속하는 부분을 별도의 2차원 배열에 담아 각각의 정답과 다른 칸이면 각 경우(검은색으로 시작하거나 흰색으로 시작하거나)의 칠해야 하는 갯수를 1씩 증가시켜 더 작은 수를 리턴하도록 했..
-
[Python 3] BOJ - 1654 "랜선 자르기"BOJ 2020. 3. 8. 21:57
# 문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net # 풀이 : 개인적으로 문제의 핵심은 갯수를 기준으로 길이를 구하는것이 아니라 길이를 기준으로 갯수를 확인하는 것이다. 이는 이분 탐색을 하기 위함이다. 예를 들어 전체 랜선의 길이가 1, 2, 3, 4, 5라고 ..
-
[Python 3] BOJ - 16562 "친구비"BOJ 2020. 3. 8. 21:19
# 문제 링크 : https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N) 다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. www.acmicpc.net # 풀이 : 모든 친구와 친구관계를 맺어야 하는 것이 목표이다. 개인적으로 문제의 핵심은 친구의 친구는 친구라는 것이다. 따라서, 친구관계를 그래프로 본다면 친구관계가 끊어질 때 까지 속한..
-
[Python 3] BOJ - 18111 "마인크래프트"BOJ 2020. 3. 7. 23:00
# 문제 링크 : https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를 www.acmicpc.net # 풀이 : Python, PyPy 모두 추가시간이 주어지지 않으므로 도중에 검사하기보다 모든 원소를 돌고나서 ..
-
[Python3] BOJ - 1011 "Fly me to the Alpha Centauri"BOJ 2020. 3. 6. 23:53
# 문제 링크 : https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 www.acmicpc.net # 풀이 : 개인적으로 문제의 핵심은 가장 마지막의 이동거리는 1광년이라는 ..