판교의 메타몽

문제 링크 : www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 이 문제는 백준 11053번 가장 긴 증가하는 부분 수열의 확장판 문제이다. 이 문제에서는 유의 사항이 하나 있다. 정답이 될 수 있는 조건의 우선 순위가 아래와 같다는 점이다. 1. 수열의 합이 크고 2. 수열은 증가하는 수열이어야 한다. 즉, 증가 길이가 무조건 길다고 정답이 아니라 증가하는 수열이면서 동시에 그 합이 커야지 정답이 될..

문제 링크 : www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 이 문제는 백준 10844번 쉬운 계단 수와 거의 동일한 유형의 문제이다. 쉬운 계단 수의 문제와 차이점은, 이 문제는 쉬운 계단 수의 문제와 달리 +-1차이의 계단수만 더해주면 되는게 아니라 어떤 계단보다 작은 수의 계단들의 총합을 모두 더해줘야한다는 점이다. 이 점을 빼면 쉬운 계단 수와 별 차이가 없는 문제이니, 자세한 설명은 생략한다. #include #..

문제 링크 : www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이 문제에 빠진 설명이 있는데, 한 칸마다 동물은 한 마리씩 배치시킬 수 있다. 문제 풀이는 다음과 같다. 1. 한 줄에 사자를 배치시키는 방법은 3가지가 있다. (1) 아예 배치를 안 시킴 (2) 첫 번째 칸에 배치 (3) 두 번째 칸에 배치 2. 사자는 가로로 세로로 붙어서 배치시킬 수 없다. 가로에 붙어서 배치시킬 수 없다는 말은 각 줄마다 2칸 모두에 사자를 한 마리씩 배치시킬순 없다는 뜻이다. 세로에 붙어서 배치시킬 수 없다는 말은, 예를 들어 n번째 줄의 첫 번째 칸에 배치시켰을 경우, n-1번째 줄의 첫 번째 칸과 n..

문제 링크 : www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 해석은 다음과 같다. 1. 11을 제곱수로 나타내는 방법은 여러가지가 있는데, 대표 예시로 아래 두개를 봐보자. 11 = 3^2 + 1^2 + 1^2 (3개 항) 11 = 2^2 + 2^2 + 1^2 + 1^2 + 1^2 (5개 항) 2. 숫자 n이 주어졌을 때, n을 제곱수로 나타낼 수 있는 항의 최소 개수를 구하라. 문제 풀이는 다음과 같다. for..

문제 링크 : www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이 문제는 백준 15990번 1,2,3 더하기 5와 동일한 유형의 문제다. n길이의 이친수를 만들기 위해서는 n-1번째 숫자가 0인지 1인지를 구분하면 된다. 문제 풀이는 다음과 같다. 1. 이차원 배열[91][2]를 선언한다. 2. 문제에 주어진 예시 값들을 토대로 1번째 길이의 숫자까지 초기화 해준다. 나는 편의상 문제에서 주어진 4번째 길이까지 배열들의 값을 초기화해줬다. 3. n..

문제 링크 : www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 '같은 수를 두 번 이상 연속해서 사용하면 안된다'라는 조건 때문에 여타 다른 DP문제처럼 [n-1]+[n-2]+[n-3]의 점화식으로는 풀 수 없다. 결국 같은 수를 두 번 이상 연속사용을 방지하려면, 어떤 숫자의 계산식에 마지막에 쓰인 숫자가 무엇인지를 생각해봐야한다. 때문에 이 문제는 마지막에 쓰인 숫자(1, 2, 3)들을 구분해서 저장할 2차원 배열로 접근해야한다. 문제 풀이는 아래의 코드를 보면 쉽게 이해할 수 있으므로, 구체적..

문제 링크 : www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 이 문제는 백준 11727번 2xn 타일링 2의 확장판이다. 문제의 출력에서 확인할 수 있듯이, 무턱대고 숫자형으로 문제에 접근했다가는 시간초과 내지는 Stack Overflow가 발생할 수 밖에 없다. 이를 방지하고자 문자열로 접근해야한다. 문제 풀이는 다음과 같다. 1. 백준 11727번과 동일하게, 이 문제의 2*n의 타일을 채울 방법은 (n-1)번째 + (n-2)번째 + (n-2) 번째 타일을 채우는 합과 동일하다. 이해가 가지 않을 경우 위의 117..

문제 링크 : www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이는 다음과 같다. 1. 1부터 n까의 카드값 배열을 입력 받는다. 2. 카드값 배열의 0번째 원소는 0으로 초기화해준다. 3. 2중 for문을 세운다. 아래 이중 for문의 해석은 다음과 같다. for(int i=2; i n; arr[0] = 0; for(int i=1; i> arr[i]; for(int i=2; i

The link : leetcode.com/problems/house-robber/submissions/ House Robber - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 전형적인 동적 프로그래밍 (Dynamic Programming = DP) 문제이다. 유사한 문제로 백준 2579번 계단 오르기가 있다. 한 자리 건너뛰는 집만 털 수 있는 조건이다보니 로직 자체는 어렵지 않았다. 다만 LeetCode 특유의 예외처리에서 몇 번의 실수를 거쳤다. (num..

문제 링크 : www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 프로그래머스 Lv3 거스름돈과 동일하다. 처음 풀었을때는 DP가 어려워 어거지로 이해했었는데, 다시 한 번 푸니 전보다는 보다 잘 이해됐다. 문제 풀이방법은 본문의 예시를 기준으로 아래 2중 for문으 도표로 풀어내면 이해할 수 있다. #include #include using namespace std; int n=0,k=0,coin[101] = {0,}, sum[10001]={0,}; ..