본문 바로가기

파이썬

 (320)
[Python] 2877번 4와 7 https://www.acmicpc.net/problem/2877 2877번: 4와 7 창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오. www.acmicpc.net 22/10/07 약간의 아이디어가 있으면 쉽게 풀 수 있는 문제로, 사람에 따라 더 쉽게 느껴질 수도 있는 문제라고 생각한다. 문제 접근 방식: 문제 해결의 가장 큰 핵심은 이진수이다. 이 아이디어는 나열하다 보니 알게 되었다. 4 7 ---- 한 자릿수(2개 있음) 44 47 74 77 ---- 두 자릿수(4개 있음) 444 447 474 477 744 747 774 777 ---- 세 자릿수(8개 있음) 7을 1로, 4를 0으로 간주하면 마치 4와 7이 채워지는..
[Python] 2661번 좋은수열 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 22/10/06 전형적인 백트래킹 문제로, 좋은 수열이 되는 조건을 잘 따라가며 시뮬레이션하면 되는 문제이다. 문제 접근 방식: 문제를 해설하기에 앞서, 먼저 N = 8일 때의 찾는 과정을 도식화한 그림을 보자. 우리는 좋은 수열 중 가장 작은 수열을 찾는 것이 목적이다. 이 그림은 이를 찾기 위해 3가지 조건을 지키면서 탐색을 진행하는 과정을 나타낸 것으로, 3가지 조건은 다음과 같다. 1. 가장 작은 수열..
[Python] 2212번 센서 / 13164번 행복 유치원 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 22/10/06 두 문제는 문제 설명과..
[Python] 2343번 기타 레슨 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 22/10/05 이분 탐색 문제로, 왜 이분 탐색으로 접근할 생각을 했냐고 묻는다면... 강의의 수가 최대 10만개이고, 강의의 길이는 최대 10000분이고, 블루레이 디스크의 최소 개수는 1개이기 때문에 가능한 블루레이의 크기는 최대 10만*10000 = 10억이다. 때문에 1분부터 10억분까지 일일이 선형으로 탐색하려면 시간이 너무 오래 걸릴 것 같아 이분 탐색으로 하기로 했다. 문제 접근 방식: 블..
[Python] 17845번 수강 과목 https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 22/10/04 전형적인 배낭 문제이다. 문제 접근 방식: 이 문제에서는 서윤이가 공부에 투자할 수 있는 시간의 한계가 존재하므로, 서윤이가 쓸 수 있는 총 공부 시간의 한계, 다시 말해 이 문제에서는 N의 값을 배낭의 한계허용치라고 생각할 수 있다. 과목의 중요도의 합이 최대가 되도록 시간을 써야 하므로, 각 과목의 중요도는 배낭에 담는..
[Python] 9084번 동전 / 3067번 Coins https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net 22/10/03 배낭 문제 중 하나인데, 1차원 ..
[Python] 21317번 징검다리 건너기 https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 22/10/03 개인적으로 굉장히 난이도에 비해 굉장히 어렵게 느껴졌던 문제로, 다른 방법으로 풀었다면 조금 쉽게 해결하지 않았을까 하는 아쉬움이 남는 문제이기도 하다. 문제 접근 방식: 백트래킹으로도 접근할 수 있는 문제이긴 하지만, 나의 경우는 DP로 이 문제를 접근했었다. 굉장히 많이 틀렸기 때문에 틀린 과정을 상세하게 설명하고자 한다. 맨 처음 풀이는 그냥 단순하게 DP[N] = N번째까지 도착했을 때, 산삼을 얻기 위해 필요한 영재의 에너지 최솟값이라고 정의를 했었다. 그리고 가장 큰 점프는 한 번만 할 수 있으므..
[Python] 11057번 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 22/10/03 전형적인 DP문제로, 나는 이차원 배열을 사용하여 문제를 해결하였다. 문제 접근 방식: 나는 DP[i][j]의 정의를 다음과 같이 정의했다. DP[i][j] = i자리 숫자일 때, j로 끝나는 오르막 수의 개수 이와 같이 정의를 하면, j가 0일 때, 1일 때, ..., 9일 때 모두 비슷한 점화식을 가진다. 오르막 수의 정의 상 이전 숫자보다 ..

티스토리툴바