본문 바로가기
728x90

Python13

백준 1463 - 1로 만들기( Python ) https://www.acmicpc.net/problem/1463 전형적인 dp유형의 문제로 입력값이 1000000개, 백만개로로 적은편이기때문에 더욱이 dp로 풀어야하는 문제임을 알 수 있다. 점화식을 찾아보자 array[1] = 0 array[2] = min(array[1] + 1, array[2//2] + 1) array[3] = min(array[2] + 1, array[3//3] + 1) array[4] = min(array[3] + 1, array[4//2] + 1) array[5] = array[4] + 1 //2와 3으로 나누어 지지 않는 경우 array[6] = min(array[5] + 1, array[6//3] + array[3]) array[7] = array[6] + 1 array.. 2022. 12. 24.
백준 11727 - 2×n 타일링 2 (Python) https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 전형적인 dp 문제 dp문제의 핵심은 점화식을 빨리찾는 수 밖에 없는거 같다. 해당 문제는 직접 그리는 방식으로 점화식을 쉽게 찾을 수 있는 것 같다. 점화식 연습을 위해서는 가능한 다양한 문제를 풀어봐야할 것 같다. 1. 입력값이 1000이므로 1001개의 배열을 생성 -> 0번 인덱스는 계산하지 않기 때문 2. 입력값 1, 2는 규칙성을 찾을 수 없으므로 값을 바로 대입 3. 점화식 찾기 n = 2 -> 3 n = 3 ->.. 2022. 12. 19.
백준 17478 - 재귀함수가 뭔가요? https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문제는 전혀 어렵지않은데 문자열을 작성하는 점이 조금은 헷갈렸다... 문자열을 연결해야하는 경우 콤마(,) 와 플러스(+)의 경우가 달랐다 콤마는 공백이 자동으로 추가되며 플러스의 경우 공백없이 연결된다 이것 때문에 6번은...제출을 다시함 ㅠㅠㅠ n = int(input()) text1 = "\"재귀함수가 뭔가요?\"" text2 = "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지.. 2022. 12. 17.
백준 1439 - 뒤집기 ( Python ) https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 초급 그리디 알고리즘 문제 거스름돈을 거슬러주는 그리디 문제랑 다른경우이다. 문제에서 2가지 경우를 나눠서 구분하므로 알고리즘도 2가지의 경우로 나눠서 짜야한다. 제한 시간 20분 풀이방법 1. 모두 1로 뒤집는 경우 혹은 0으로 뒤집는 경우로 나눠서 계산 후 각각 변수에 저장 2. 1로 뒤집는 경우 -> 첫번째 숫자가 0이면 카운트 + 1 -> 1에서 0으로 바뀔 때 카운트 + 1 3. 0으로 .. 2022. 12. 9.
백준 11047 - 동전 0 (Python) 백준 11047 동전 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 예제 풀이 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 10가지의 동전을 4200원의 최소 동전 개수를 구하려면 큰 숫자부터 값을 빼줘야 한다 4200 - 1000 = 3200 3200 - 1000 = 2200 2200 - 1000 = 1200 1200 - 200 = 200 200 - 100 = 100 100 - 100 = 0 총 6번 1.. 2022. 11. 25.
백준 11399 - ATM( Python ) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 예제 풀이 n = 5 p = [ 3, 1, 4, 3, 2 ] 적게 기다리는 순으로 우선 오름 차순 정렬을 해줘야한다 sorted = [ 1, 2, 3, 3, 4 ] 1 1 + 2 = 3 1 + 2 + 3 = 6 1 + 2 + 3 + 3 = 9 1 + 2 + 3 + 3 + 4 = 13 => 1 + 3 + 6 + 9 + 13 = 32 즉, 1부터 이전 값을 계속 반복하며 더하는 문제이다. 2중 for문으로 해결이 가능하다 n = .. 2022. 11. 23.
728x90
반응형

티스토리툴바