본문 바로가기

전체 글

 (2341)
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 11722번:가장 긴 감소하는 부분 수열 답 algorithm헤더가 필요한 *max_element()함수를 사용해 풀었습니다. *max_element(배열.begin(),배열.end())무조건 시작은 0번째 인덱스부터 입니다.123456789101112131415161718192021222324#include #include #include using namespace std;int main() { int n; cin >> n; //*max_element(배열의처음(*0번째 인덱스 부터 시작한다).begin(),끝.end()) vector a(n); vector d(n); for (int i = 0; i > a[i]; for (int i = 0; i
(C++) - 백준(BOJ)코딩 2579번 : 계단오르기 답 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2차원 bottom up dp로 풀었습니다 풀이방법 1. 각 계단을 stair[i]로 입력 받습니다. 2. 점화식을 생각합니다. i번째 계단을 올라갔을 때 몇 번 연속해 올라가 있는지에 대한 상태가 필요하므로 2차원 배열 d를 선언합니다. d[i][j] = i번째 계단을 j번 연속으로 올라갈 때 최대값 d[i][1] => 1번 연속으로 올라갔으므로 i-2번째 계단은 올라가거나 건너뛰거나 상관없습니다. 따라서 다음 점화식을 ..
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 9465번:스티커 답 #include #include using namespace std;int D[100001][3], A[100001][2];int main() {int n, T;int ans = 0;cin >> T;for (int k = 0; k > n;for (int i = 0; i A[j][i];}}D[0][0] = D[1][0] = D[2][0] = 0;for (int i = 1; i
(C++, Python3) - 백준(BOJ) 11055번 :가장 큰 증가 부분 수열 답 https://www.acmicpc.net/problem/11055dp문제였습니다.📕 풀이방법📔 입력 및 초기화배열길이 n과 배열을 arr를 선언 후 입력받습니다.📔 풀이과정완전 탐색으로 i까지 도달했을 때 가장 큰 증가 부분 수열의 값을 d[i]라 하면 다음과 같은 점화식이 가능합니다. $${ if \ arr[i] > arr[j] \ D[i] = MAX(D[j](0arr[i]가 가장 큰 값이므로 그보다 작은 arr[j]를 발견할 경우 그때의 D[j]값에서 현재 선택 값인 arr[i]를 더한 값의 최댓값을 d[i]에 저장하면 됩니다. n이 1000까지이므로 O(N^2)로 동작 가능한 풀이입니다.📔 정답 출력 | 반환정답 배열의 가장 큰 원소를 반환합니다.📕 Code📔 C++#include ..
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 11053번:가장 긴 증가하는 부분 수열 답 //가장 긴 증가하는 부분수열의 길이를 D//D[i] = A[1],A[2],...,A[i]; i가 마지막으로 수열이 끝날 때의 D의 길이 = D[i]//A[i]>A[j] 이고 D[j] > D[i] 일 때 D[i] = D[j]12345678910111213141516171819202122232425#include #include #include using namespace std;int main() { int n; cin >> n; vector A(n); for (int i = 0; i> A[i]; } vector D(n); for (int i = 0; i
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1912번:연속합 답 //연속 합에서 가장 큰 수를 구할 때는 두 가지 경우로 나눌 수 있다//1.자기 자신만 더했을 때 가장 큰 경우//2.연속 된 두 수를 더했을 때 가장 큰 경우//D[i] = i번째 수로 끝나는 가장 큰 연속 합//K[] = 입력된 수//D[i] = D[i-1] + K[i] 와 K[i]와 비교했을 때 가장 큰 것. 12345678910111213141516171819202122232425262728293031#include #include #include using namespace std;int main() { int n, big = 0; cin >> n; vector D(n); vector K(n); for (int i = 0; i > K[i]; } for (int i = 0; i
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1699번:제곱수의 합 답 //O + O + ... + j^2 = i일 때..//D[i] = 합의 최소 개수//i-j^2 = O+O+O...+O//그러므로 D[i] = min(D[i],D[i-j^2]+1)1234567891011121314151617181920#include #include using namespace std;int D[100001];int main() { int N; cin >> N; for (int i = 1; i
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 11052번:붕어빵 판매하기 답 //D[i] = 붕어빵 i개를 팔았을 때 얻을 수 있는 최대 수익//P[i] = 붕어빵 세트를 팔았을 때 얻을 수 있는 수익//마지막 j를 팔 때 최대 수익을 남길 수 있다면 j를 제외한 나머지 붕어빵 개수는 i-j개//D[i-j]에 나머지 P[j]를 더하면 D[i]가 된다.//모든 경우의 수를 살펴봐 가장 큰 값이 최대 수익이 된다.// D[i] = max(D[i],P[j]+D[i-j])123456789101112131415161718#include #include using namespace std;int main() { int N,big = 0; cin >> N;//남은 붕어빵 int *D = new int[N + 1]; int *P = new int[N + 1]; for (int i = 1; i ..

티스토리툴바