그랬었습니다

이 문제 역시 Dynamic Programming으로 해결해야 한다. 이 문제는 문제 그대로 큰 숫자를 나누고, 빼면서 접근하면 안 된다. 만약 그렇게 한다면 숫자가 3과 2로 나누어 떨어지는지 검사하는 데에만 엄청난 리소스가 낭비된다. 반대로 생각해보자. 2로 나누어 떨어지는 수는 2로 나눈 몫의 2배와 같은 값이다. 3으로 나누어 떨어지는 수는 3으로 나눈 몫의 3배와 같은 값이다. 그렇다면 역으로 작은 수에 2나 3을 곱하고, 1을 더하면서 숫자를 늘려가면 된다. 1부터 시작한다. 1의 3배는 3이다. 한 번의 연산이니 1을 입력한다. 1의 2배는 2이다. 한 번의 연산이니 1을 입력한다. 1+1은 2이다. 그런데 2에는 이미 숫자가 입력되어 있다. 비교 후 더 작은 값을 넣는다. 이렇게 하면 배열..

계단을 오르는 방법은 2가지 방법이 있다. 한 계단씩 오르는 방법과 두 계단씩 오르는 방법. 그리고 제약조건으로 "연속된 세 개의 계단을 모두 밟아서는 안된다."가 있다. 조금 관점을 바꿔서, 올라올 계단의 입장에서 보자. 올라오는 방법은 한 계단 아래에서 올라오는 방법과 두 계단 아래에서 올라오는 방법이 있다. 그리고 s[i][1]을 "가장 마지막에 한 계단 아래에서 올라와서 i번째 계단으로 올라갔을 때의 최고 점수"라고 정의하자. s[i][2]는 "가장 마지막에 두 계단 아래에서 올라와서 i번째 계단으로 올라갔을 때의 최고 점수"이다. 그럼 s[i][1]을 살펴보자. 한 계단 아래에서 올라왔다. 즉 i - 1번째 계단과 i번째 계단을 밟았다는 것이다. 따라서 이 방법을 골랐을 경우에는 i - 1번째 ..

또 다른 동적 계획법 문제인 RGB거리와 크게 다르지 않은 문제이다. RGB거리 문제를 이해할 수 있다면 크게 어렵지 않게 이해할 수 있을 것이다. https://everyyy.tistory.com/69

백준에서 단계별로 풀기를 위에서부터 100 문제 정도 풀면 동적 계획법이 나온다. 동적 계획법1 파트에서 4번까지는 피보나치 같은 비교적 간단한 문제만 나온다. 여기까지는 알고리즘에 대한 공부를 따로 하지 않아도 직관으로 어느 정도 풀 수준이라고 할 법하다고 생각한다. 하지만 이 문제는 대중적? 알고리즘의 한 부분인 Dynamic Programming을 공부하지 않으면 꽤나 고전할 법한 문제이다. 물론 따로 공부하지 않았다고 해서 풀지 못할 문제라는건 아니지만.. 여하튼 이 문제는 동적 계획법을 처음 공부한 사람이 익숙해지기 위해 풀어보는 입문용 문제라고 봐도 좋을 것 같다. 자 이제 문제를 살펴보자. i번째 집은 i-1번째와 i+1번째 집과 같은 색으로 칠할 수 없다. 1번째 집부터 차례대로 집의 색을..

123456789101112131415161718192021222324252627282930313233//#define _CRT_SECURE_NO_WARNINGS#include using namespace std; long long wave(int input); int main() { int N; cin >> N; for (int i = 0; i > input; cout

123456789101112131415161718192021222324//#define _CRT_SECURE_NO_WARNINGS#include using namespace std; int fib(int n); int main() { int N; cin >> N; cout

그냥 n번째 피보나치 수를 계산하는 문제가 아니다. n번째 피보나치 수를 재귀 함수로 구할 때, fib(0)과 fib(1)이 몇 번씩 호출되는지를 묻는 문제다. 근데 딱히 다를 건 없다. 동적 계획법으로 푸는데, 누적하는 수가 피보나치 수가 아니라 0과 1의 회수일 뿐이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 //#define _CRT_SECURE_NO_WARNINGS #include using namespace std; void fib(int n); int main() { int n; cin >> n; for (int i = 0; i >..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 //#define _CRT_SECURE_NO_WARNINGS #include using namespace std; unsigned long long fib(int n); int main() { int n; cin >> n; cout

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647//#define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std; class Client {private: int age, order; char name[101];public: void setInfo(int age, char* name, int order) { int i; this->age = age; for (i = 0; name[i] != NULL; i++) this->name[i] = name[i]; this->name[i] = NULL; this->order = orde..

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556//#define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std; class Text {private: string text;public: void setText(string text) { this->text.clear(); this->text.append(text); } bool operatortext.length() text.length() == text.text.length()) { for (int i = 0; i text.length();..