문제 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, ..
Koala - 9기/코딩테스트 준비 스터디
문제 https://www.acmicpc.net/problem/14495 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net 코드 풀이 f(n)=f(n-1)+f(n-3)을 n의 범위인 116 안에서 반복문을 돌려 리스트를 미리 만들어놓는다. f[0]부터 첫번째 숫자가 들어가므로 n-1항의 값을 출력한다.
https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 최장 증가 부분순열 문제. 이때 최장 증가 부분순열이란 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열 이는 동적 계획법 문제로, dp 테이블을 만들어 풀이할 수 있다. 모든 원소가 1인 DP 테이블을 만들어주고, 조건에 ..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 분석 분류 다이나믹 프로그래밍, DP 문제 설명 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 각각의 상담은 상담을 완료하는 데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성해 보자. 입력 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며,..
https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 문제 분석 분류 DP 문제 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다. 버튼을 K번 ..
https://www.acmicpc.net/problem/10707 10707번: 수도요금 JOI군이 살고 있는 지역에는 X사와 Y사, 두 개의 수도회사가 있다. 두 회사의 수도요금은 한 달간 수도의 사용량에 따라 다음과 같이 정해진다. X사 : 1리터당 A엔. Y사 : 기본요금은 B엔이고, 사용량 www.acmicpc.net 코드 a = int(input()) b = int(input()) c = int(input()) d = int(input()) p = int(input()) c1 = a * p if c < p: c2 = b + ((p - c) * d) else: c2 = b if c1 < c2: print(c1) else: print(c2) 풀이 x사를 이용할 때의 요금과 y사를 이용할 때의 요금..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자...
문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 정답코드 # 동전 1 # 복습횟수:0, 02:00:00 import sys si = sys.stdin.readline N, K = map(int, si().split()) dp = [0] * (K+1) dp[0] = 1 # coin ..
문제 분석 해당 문제의 시간 복잡도는 0.5초이고, 메모리 제한은 4MB이다. 메모리가 굉장히 적으므로 주어진 n 크기로 2차원 배열을 만들 경우, 메모리가 초과된다. 즉, 최대 공간 복잡도가 n을 사용할 경우 사용할 수 있는 자료구조는 일차원 배열 정도이다. 1차원 배열이라는 제한에서 사용할 수 있는 알고리즘 수는 많지 않다. 이와 같은 상황을 고려하여, DP를 통해 문제를 해결해야 겠다고 생각했다. 문제 풀이 DP는 이전에 구했던 답을 이용하여 현재의 답을 도출하는 알고리즘이다. 그렇다면, 우리가 구해야 할 경우의 수를 이전 값을 통해 현재 값을 도출하는 형태로 구현할려면 어떤 값을 기준으로 DP를 구성해야할까. 해당 문제는 동전의 합이 k가 되도록 하는 경우의 수이다. k값에 따라 동전의 경우를 구..
문제 https://www.acmicpc.net/problem/2565 Algorithm 전깃줄이 교차하지 않기 위해서는 어떤 형태로 배치되어야 하는지 파악하는 것이 핵심이다. "연결되어 있는 B의 번호들이 오름차순을 이룬다면, 전깃줄은 교차하지 않는다." 위 아이디어만 파악했다면, 다음 과정을 차례대로 수행한다. 1. 문제에서의 그림과 같은 형태로 전깃줄을 배치하기 위해, A 전봇대의 번호를 기준으로 오름차순 정렬한다. 2. 이제 B에 연결된 전깃줄들이 오름차순을 이루어야 하므로, 가장 긴 증가하는 부분 수열의 길이를 구한다. 여기서, 가장 긴 증가하는 부분 수열의 길이를 구하는 과정은 다음과 같다. 1. 이전 지점보다 현재 지점의 값이 크다면, 현재 지점까지의 증가하는 부분 수열의 길이가 1 증가한다..
https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 1. 문제 요약 강 서쪽에는 N개의 사이트, 동쪽에는 M개의 사이트가 있다. 서쪽 사이트와 동쪽 사이트를 연결하여, 서쪽 사이트 개수만큼(N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다. 이 때, 다리를 지을 수 있는 경우의 수는? 2. 문제 접근 N, M개의 사이트 간의 연결을 "더 적은 개수의 사이트 간의 연결"들의 합으로 표현할 수 있다고 판단하여, DP를 사용하기로 하였습니다..
https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 1. 문제 접근 아이고 이거 문제 태그 없었으면 큐로 줄 빙글빙글 돌릴뻔 했습니다. 역시 DP는 바로바로 문제를 파악할 수 있는 능력이 있어야 할 것 같아요. 여러 학생이 서있고, 최소한의 자리 바꿈으로 1~N까지 줄을 세우려면요, 최대한 많은 학생을 제자리에 고정시켜놓아야 합니다. 예를 들어, 학생들이 다음과 같이 줄을 서있다고 합시다. 1 2 4 5 3 6 7 1번, 2번, 4번, 5번, 6번, 7번..
