Category: problems

2018
0
computer sciencealgorithms

백준[11054] - 가장 긴 바이토닉 부분 수열

문제백준 11054 문제 보기 접근 방법먼저 증가하는 부분 수열을 구하는 dp을 작성하고 뒤에서 부터 감소하는 가장 긴 부분 수열을 구하는 dp2를 구한다.따라서 dp - dp2 - 1에서 최대값을 출력한다. -1을하는 이유는 dp[2] + dp2[2]를 계산하면 2번째 인덱스가 중복 계산되기 때문이다. 코드#include <iostream> #in

0
computer sciencealgorithms

백준[2156] - 포도주 시식

문제백준 2156 문제 보기 접근 방법경우를 총 3가지로 나누어 dp로 해결한다. n번째 포도주를 마시지 않을 때와 마실 때(첫번째 잔인지, 연속된 잔인지 구분).n번째 잔을 마시지 않을 경우, n-1번째 잔은 마셧는지 안마셧는지 여부에 상관없이 최대값을 저장.n번째 잔이 연속된 첫 잔일 경우, 이전 잔은 무조건 마시지 않었어야 한다.n번째 잔이 연속된 잔

0
computer sciencealgorithms

백준[10844] - 쉬운계단수

문제백준 10844 문제 보기 접근 방법바로 앞의 수가 0과 9일때 주의해서 점화식을 세운다. 처음 제출할 때 출력할때만 나머지를 계산해서 출력되도록해서 오버플로우 발생으로 오답이 됐다.점화식은 자릿수와 바로 앞의 숫자를 인덱스로 모든 경우를 저장한다.if(앞에 저장된 숫자가 0) dp[i][j] = dp[i - 1][1];if(앞에 저장된 숫자가 9) d

0
computer sciencealgorithms

백준[11726] - 2*n 타일링

문제백준 11726 문제 보기 접근 방법bottom-up 방식의 dp를 활용해 문제 접근을 했다. 길이가 1인 타일이 추가될 때와 2인 타일이 추가될때의 경우를 계산해 식을 세웠다.점화식은 다음과 같다.dp[n] = dp[n-1] + dp[n-2] 코드#include <iostream> using namespace std; int n; int d

0
computer sciencealgorithms

백준[11836] - 여왕벌

문제백준 10836 문제 보기 접근 방법초반에 문제를 잘못 이해해 엄청 틀렸다.. 첫날부터 순서대로 입력이 되는건데 내맘대로 순서대로라는 단어를 빼고 읽었다. 문제 접근 방법은 먼저 map[1][1]을 구해야 이후의 행을 구할 수 있다.행 하나하나를 계산하면서 진행하면 시간초과가 남으로 먼저 맨 왼쪽 행과 맨 위쪽 열만 받아 저장하고 나머지 영역은 맨 윗

0
computer sciencealgorithms

백준[10835] - 카드놀이

문제백준 10835 문제 보기 접근 방법dfs를 사용해서 경우를 잘 나누면 문제를 해결할 수 있음. 근데 N이 크다보니 메모이제이션 방법으로 중간값을 계속 저장해야 함. 시간 초과가 나지 않을까 걱정했는데 다행히 통과. 코드#include <iostream> using namespace std; int N; int box[2001][2001];