본문 바로가기

ps45

[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.
[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.

티스토리툴바