링크 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 소요시간 : 7분 52초 설계하기(접근방법) 1. 입력받기 테스트 케이스 개수와 n을 입력받는다 2. 구현하기 n 이 1~ 100까지 들어오니 dp를 100까지 선언해준다 그림을 주어서 편하게 문제를 풀 수 있었다 그림을 보면 다음 정삼각형의 길이는 직전의 정삼각형의 길이 : dp[n-1] 5번쨰 전의 정삼각형의 길이 : dp[n-5]의 길이를 합한 것을 볼 수 있다 3. 출력하기 dp[..
링크 : https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 소요시간: 16분 50초 설계하기(접근방법) 1. 입력받기 n을 입력받는다 2. 구현하기 이친수를 써보니 피보나치 수열의 형태가 나타났다 왜 dp[n] = dp[n-1] + dp[n-2]의 형태가 나타날까??? 새로운 이친수를 구할 때 우리는 끝이 0 아니면 1인 케이스로 나눌 수 있다 끝이 0인 케이스는 dp[n-1]의 케이스에서 어느곳이든 0을 붙일 수 있기 때문에 d..
링크 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 소요시간: 1시간 25분 설계하기(접근방법) 1. 입력받기 2. 구현하기 접근법으로 알아낸 것이 아닌 수열을 그려보며 알게 되었다. n과 k 의 형태는 0이 없는 경우에는 k가 n 미만일 때는 파스칼의 삼각형 형태를 보인다 n = 5, k = 3일 때는 1 1 3 / 1 3 1 / 3 1 1 1 2 2/ 2 1 2/ 2 1 1 로 6개다 여기서 0이 추가된다면 어떻게 될까? 각 수열의 자리에 0 이 들어가는 경우를 생각하면 k = 1일 때에다가 0을 2개 추가한 수열 k = 2일 때에다가 0을 1개 추가한 수..
링크 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 소요시간: 18분 12초 설계하기(접근방법) 1. 입력받기 배열을 입력받는다 2. 구현하기 이 문제의 핵심 포인트는 가장 긴 산을 만드는 것이다 산이라고 하면 4 3 2 2 1 1 와 같은 형태일 것이다 가장 긴 증가하는 부분 수열은 쉽게 구할 수 있다 dp를 선언하여 현재 자신의 값보다 작은 값 중 dp의 길이가 최대값이었던 dp에 +1을 해주면 된다 같은 방식으로 가장 긴 감소하는 부분 수열도 쉽게..
링크 : https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 소요시간: 27분 설계하기(접근방법) 1. 입력받기 카드 팩 리스트를 입력받는다 2. 구현하기 이전에 풀었던 DP 문제와 유사하다 중복되는 조합이 있으면 가장 작은 케이스부터 dp를 처리하고 가장 큰 숫자를 마지막으로 dp를 처리하여 카드 수를 뽑을 때 최대값을 구한다 3. 출력하기 최대값을 출력한다 코드(출력) n = int(input()) pack = list(map(int, input..
링크 : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 소요시간: 31분 25초 설계하기(접근방법) 1. 입력받기 무게와 가치를 입력받는다 2. 구현하기 이 문제는 최대 무게까지 각 무게별로 어떻게 넣어야 최대의 가치가 되는지 구하면 된다 즉 검사를 할 때 dp[i + w] < dp[i] + v 일때 dp[현재 무게 + 넣을 물건의 무게]의 값어치가 dp[현재 무게] 의 ..
링크 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 소요시간: 1시간 실패 설계하기(접근방법) 1. 입력받기 문자를 입력받는다 2. 구현하기 이 문제는 이중배열을 만들어서 두 문자를 비교한다 A와 CAPCAK 011111 AC와 CAPCAK 011222 ACA와 CAPCAK 011233 .... 이런 방식으로 이전 배열에서 새로운 같은 글자가 나타난 경우 +1을 해준다 이러한 방식으로 가장..
링크 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 소요시간:25분 실패 설계하기(접근방법) 1. 입력받기 전깃줄 리스트를 입력받는다 2. 구현하기 현재 왼쪽 전깃줄을 기준으로 그 전 전깃줄 중 최대값을 가져오면 될 것 같았는데 어떻게 우측 값을 조절해야하는지 떠올리질 못했다 현재 전깃줄을 기준으로 첫 전깃줄 부터 최대값을 비교한다 그 중 현재 전깃줄의 우측 값보다 작은 값들로만 비교한다 우측 값이 현재보다 작다면 비교하는 전깃줄의 dp(이..
