본문 바로가기

백준47

[Python] 백준 20056 마법사 상어와 파이어볼 문제 링크 : https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 1. 접근 방법 빡빡한 구현이 필요한 상어 문제를 처음 접했을 때는 많이 막막했었다. 코드를 구현하는 과정뿐만 아니라, 적절한 자료구조, 알고리즘을 잘 다루지 못해서 더욱 막막했었던 것 같다. 그러나 시간이 지나고, 문제를 코드로 구현하는 과정과, 자료구조, 알고리즘을 잘 다루기 시작하며 보다 수월하게 문제를 해결하는 것 같다. 2. 풀이 코드.. 2021. 10. 25.
[Python] 소가 길을 건나간 이유 7 문제 링크 : https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 7 30에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다. www.acmicpc.net 1. 접근 방법 최단거리 문제인데, 사이클과 방문한 위치를 여러 번 방문할 수 있는 문제여서 다익스트라로 접근했다. 여러 차례 시행착오를 거쳤는데, 완전 탐색이 되지 않도록 하는 것이 이 문제의 핵심인 것 같다. 2. 풀이 코드 🖥python 코드 import heapq import sys input = sys.stdin.readline MIIS = lambda: .. 2021. 10. 25.
[Python] 백준 21608 상어 초등학교 문제 링크 : https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 1. 접근 방법 구현의 난이도가 낮지는 않지만, 조건 분기가 많지 않아서 비교적 어렵지 않게 구현할 수 있을 것이라 생각한다. 구현 문제는 문제만 잘 읽는다면, 한 번에 해결할 수도 있는 문제 종류라고 생각한다. 2. 풀이 코드 🖥python 코드 import sys input = sys.stdin.readline def search_friends(student: int,.. 2021. 10. 22.
[Python] 백준 16926 / 16927 배열 돌리기 1, 2 문제 링크 배열 돌리기 1 : https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 배열 돌리기 2 : https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3.. 2021. 10. 12.
[Python] 백준 10835 카드게임 문제 링크 : https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 1. 접근 방법 각 차례마다 할 왼쪽 카드, 오른쪽 카드, 양쪽 카드를 버리를 행동을 할 수 있다. 오른쪽 카드를 버릴때만 조건이 있고, 점수를 얻을 수 있어서 모든 카드쌍에 대한 경우의 수를 탐색하지는 않을 것이다. 그래도, 각 카드가 최대 2000개씩이므로, DFS와 DP두가지 방법을 고민했다. 깊어야 4000번 들어가고, 더 깊게 탐색하지 않을 것 같.. 2021. 10. 10.
[Python] 백준 1398 동전 문제 문제 링크 : https://www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 www.acmicpc.net 1. 접근 방법 기본적인 접근은 거스름돈 문제처럼, 해당 금액을 가장 큰 금액으로 채우는 것으로 시작했다. 그런데, 10과 25가 약수 / 배수 관계가 아니라서 일반적인 방법으로 해결하지 못한다. (30일 때, 10 + 10 + 10이 최소이지만, 큰 값 부터하면 25 + 1 + 1+ 1+ 1+ 1으로 최소가 아니게 됨) 그래서 전반적인 .. 2021. 10. 8.
[Python] 백준 9080 PC방 요금 문제 링크 : https://www.acmicpc.net/problem/9080 9080번: PC방 요금 현성이는 요즘 LINEAR 2라는 온라인 게임에 빠져있다. PC방에 가서 게임을 즐기는데, 자주 가는 PC방의 요금체계는 다음과 같다. 일반 요금으로 시간당 1000원 씩을 받으며, 야간 정액을 끊으면 5000원 www.acmicpc.net 1. 접근 방법 주간과 야간을 나누고, 야간에는 일반 요금과 야간 정액이 있어 적어도 3가지를 고려해야 할 것 같았다. 진행하며 보니 더욱 안정적으로 풀이하기 위해 더욱 많은 분기점이 생겼다. 하지만 큰 토대는 주간과 야간 그리고 하루가 넘어가는 것을 어떻게 잘 처리하는지인 것 같다. 그리고, 시간, 분을 각각 저장해도 되지만, 나는 00:00 기준으로 지난 시간.. 2021. 10. 7.
[Python] 백준 2572 보드게임 문제 링크 : https://www.acmicpc.net/problem/2572 2572번: 보드게임 첫째 줄에 카드의 수 N이 주어진다. 둘째 줄에 N장의 카드의 색깔이 번호 순서대로 빈칸을 사이에 두고 주어진다. 셋째 줄에는 마을의 수 M과 길의 수 K가 빈칸을 사이에 두고 주어진다. 이어 K개 www.acmicpc.net 1. 접근 방법 처음에는 문제를 잘못 읽어 너무 많은 경우의 수가 아닌가 하는 생각을 했다. 카드를 순서대로 뽑으며 각 이동하는 모든 경우의 수를 계산해야 되고, 최대 탐색 마을의 수와 카드의 수가 적지 않아 DP와 DFS 중 고민했다. 그런데 길의 수가 마을에 비해 너무 많아 DP가 더 적절할 것 같아 DP로 접근했지만, 쉽지는 않았다. 2. 풀이 코드 🖥python import.. 2021. 9. 21.
[Python] 백준 12787 지금 밥이 문제냐 문제 링크 : https://www.acmicpc.net/problem/12787 2021. 9. 20.

티스토리툴바