본문 바로가기

CS/알고리즘 & 문제풀이53

[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.
[Python] 백준 6568 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다 문제 링크 : https://www.acmicpc.net/problem/6568 6568번: 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다 그래서 여러분도 크리스마스날 심심해서 컴퓨터를 하나 만들었다. 이 컴퓨터는 아주 적은 수의 명령어를 사용하는 하나의 프로세서, 32바이트 메모리, 8비트짜리 가산기, 5비트짜리 프로그램 카 www.acmicpc.net 1. 접근 방법 처음 문제를 읽고 잘 이해하지 못해 많이 당황했다. 이번 문제는 잘 읽고 이해하는 것부터 시작했다. 컴퓨터의 이론과도 연관 있는 것 같아, 관련한 내용을 공부하면 좋을 것 같다. 2. 해결 코드 python 코드 import sys input = sys.stdin.readline while True: try: memory = .. 2021. 9. 19.
[Python] 백준 1338 알 수 없는 번호 1. 접근 방법 입력을 '잘' 처리했다면 문제는 매우 간단하다. 정답 가능성인 수를 하나 선택하고, 그러한 가능성이 있는 수가 2개 이상인지, 아니면 해당 범위에 속하지 않는지를 확인하면 끝난다. 이 내용만 있다면 문제 난이도는 실버 이하로 책정되어도 괜찮을 것 같다. 하지만, 더욱 중요한 부분이 많이 남아있다. 2. 해결 코드 파이썬 코드 st, end = map(int, input().split()) if st > end: st, end = end, st x, y = map(int, input().split()) if x = x or y < 0: print('Unknwon Number') else: # 만족하는 수 찾기 m.. 2021. 9. 18.
[Python] 백준 5052 전화번호 목록 문제 링크 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 1. 접근 방법 가장 쉬운 방법은 각 전화번호를 길이별 오름차순 정렬하여 해결하는 방법이다. 각 테스트 케이스 별 입력도 10000개 이고, 정렬, 탐색을 고려한다고 해도 더 빠르게 작동할 것이다. 하지만 이번 문제는 트라이 알고리즘으로 해결하고 싶었다. 처음에는 무슨 알고리즘인가 하여 찾아보고 고민도 했는데, 오히려 구현은 이러한 과정보다 더 쉽게 해결됐다... 2021. 9. 15.
[Python] 백준 9655 돌 게임 문제 링크 : https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. 접근 방법 작은 숫자부터 시작해서 규칙성을 찾는 것으로 시작했다. n = 1일 때, 상근이가 시작하므로, 무조건 상근이가 이기게 됨 n = 2일 때, 상근이는 하나만 가져갈 수 있고, 나머지 하나를 창영이가 가져가므로 창영이가 이기게 됨 n = 3일 때, 상근이가 3개를 가져가면 이길 수 있지만, 1개를 가져가면 창영이가 이는 결과가 나옴. '완벽하게' 게임을 했다는 가정이 있으므로 상근이가 3개를 가져가서 이기게 됨 n = 4일 때, 상근이가 1개, 3개를 가져가는 경우가 있음. 1개를 가져가서 .. 2021. 9. 12.

티스토리툴바