11053번: 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열사용 언어: C++ 문제 요약수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이dp[i]는 해당 위치에서 가장 긴 증가하는 부분 수열의 길이.dp[i]의 값은 이전 위치 j들 (0그래서 점화식은dp[i] = max(dp[j] +..

2156번: 포도주 시식

2156번: 포도주 시식사용 언어: C++ 문제 요약효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 ..

10844번: 쉬운 계단 수

10844번: 쉬운 계단 수사용 언어: C++문제 요약45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.풀이이전 자리 숫자와 현재 자리 숫자의 관계를 고려하면 되므로 마지막 숫자만 알면 다음 숫자 선택이 가능. 그래서 점화식 기반 Bottom-Up DP로 채워나가는 식으로 풀어야하고, dp[i][j]는 길이 i, 마지막 숫자 j일 때 계단 수의 개수.점화식- dp[i][j] = dp[i - 1][..

2579번: 계단 오르기

2579번: 계단 오르기사용 언어: C++ 문제 요약계단은 아래에서 위로 올라가며, 각 계단에는 점수가 적혀 있음.계단은 1칸 또는 2칸씩 오를 수 있음.단, 연속된 3개의 계단을 모두 밟는 것은 금지됨.마지막 계단은 반드시 밟아야 함.시작점은 계단에 포함되지 않음.주어진 계단 점수 배열에서, 규칙을 지키며 밟을 수 있는 최대 점수의 합을 구하는 문제. 풀이처음엔 재귀로 풀어보려 했지만 연속된 3계단을 밟을 수 없다는 제약 때문에 코드가 복잡해졌고,"더 좋은 방법이 있겠지" 싶어서 Bottom-Up DP 방식으로 전환했다. dp[i] = i번째 계단까지 도달했을 때의 최대 점수두 가지 경우만 고려한다:dp[i-2] + stairs[i] → 한 칸 건너뛰고 오기dp[i-3] + stairs[i-1] + s..

1932번: 정수 삼각형

1932번: 정수 삼각형사용 언어: C++ 문제 요약 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.풀이문제 예시를 보면 위에서 아래로 가는 그리디 방식은 안된다 -> 전체합이 최대값이 된다는 보장이..

9184번: 신나는 함수 실행

9184번: 신나는 함수 실행사용 언어: C++ 문제 요약재귀 호출만 생각하면 신이 난다!다음과 같은 재귀함수 w(a, b, c)가 정의되어 있다:if a 20 or b > 20 or c > 20: return w(20, 20, 20)if a 입력:여러 줄에 걸쳐 정수 a b c가 주어진다.모두 -1일 경우 입력 종료.출력:각 입력에 대해 w(a, b, c) = 결과값 형식으로 출력한다.문제의 함정재귀함수 구현 자체는 쉽지만,w(15, 15, 15) 같은 값은 수백만 번 호출되는 중복 재귀가 발생한다.그대로 구현하면 시간 초과 혹은 시간 폭탄.풀이메모이제이션 (Memoization)한 번 계산한 결과는 배열에 저장해두고다음에 같은 입력이 오면 즉시 반환한다.dp[a][b][c] 배열을 사용해서 캐..

14889번: 스타트와 링크

14889번: 스타트와 링크사용 언어: C++ 문제 요약총 N명의 사람이 있고, 이들을 두 팀(스타트 팀, 링크 팀)으로 나눈다. 각 팀에 속한 사람들의 능력치 합 차이를 최소화하는 것이 목표.능력치는 2차원 배열 S[i][j]로 주어지며,i번과 j번이 같은 팀일 때 더해지는 값은 S[i][j] + S[j][i].N은 항상 짝수이며, 두 팀은 N/2명씩 구성돼야 함.풀이1. 조합을 통해 팀을 나눈다N명 중 N/2명을 선택해서 스타트 팀을 구성하면,나머지 인원은 자동으로 링크 팀이 된다.→ 즉, 전체 경우의 수는 NC(N/2) 개의 조합.2. 각 조합에 대해 능력치 차이 계산스타트 팀의 능력치 = sum(S[i][j] + S[j][i]) (for i, j in 스타트 팀)링크 팀도 동일하게 계산두 팀의 차..

14888번: 연산자 끼워넣기

14888번: 연산자 끼워넣기사용 언어: C++ 문제 요약N개의 수와 N-1개의 연산자가 주어짐.수의 순서를 바꾸지 않고, 주어진 연산자를 모두 사용해 수식을 완성.연산 순서는 앞에서부터(왼쪽에서 오른쪽으로) 진행.가능한 모든 수식 결과 중 최댓값과 최솟값을 출력해야 함.풀이가능한 연산자 순열을 모두 탐색해야 하므로 백트래킹(DFS) 을 사용.각 재귀 단계마다 남아 있는 연산자 중 하나를 선택해 현재까지의 계산 결과를 갱신.나눗셈은 음수 처리를 주의해야 함 (C++ 기준: -(-a / b) 방식으로 처리).#include #include #include using namespace std;int N;vector A;int op[4]; // +, -, *, /int max_val = -1e9;int min..