궤도

문제 풀이 동적계획법 문제의 수많은 유형 중 하나이다. 이런류의 문제를 처음 봤다면 어렵겠지만, 몇 개 풀어보고 나면 그 문제가 그 문제라 원활하게 풀 수 있다. 각 index에서의 최댓값을 m_max에 저장한다. 그럼 이제 m_max에 값이 어떻게 들어가는지 살펴보겠다. m_max[1] : 돈이 1개라면 그냥 그걸 주워가면 된다. 그러므로 m_max[1] = m[1] m_max[2] : 돈이 2개여도 그걸 다 주워간다 해서 규칙을 어기진 않는다. 그러므로 m_max[2] = m[1] + m[2] m_max[3] : 돈이 3개라면 이제 모든 돈을 주워갈 수는 없다. 3개 중 금액이 가장 커질 수 있는 2장을 가져가자. (근데 코드는 왜 [1]+[2]를 까먹었지? 실수한 것 같다.) m_max[n] (n>..

문제 풀이 너무 어렵게 생각해서 시간이 좀 걸렸다. 단순하게 생각하면 된다. 양끝을 서로 비교한다. 그럼 이 셋 중 하나일 것이다. 1. 양끝 숫자가 같다. 2. 왼쪽 숫자 오른쪽 숫자 1번의 경우라면 회문 조건을 충족하니 한칸씩 안으로 들어가면 된다. 2번의 경우라면 왼쪽 숫자가 커지도록 인접한 숫자와 더해주고, 3번의 경우라면 오른쪽 숫자가 커지도록 인접한 숫자와 더해준다. 재귀함수로 구현했는데, 반복문으로 구현해도 어려움은 없을 것 같다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include int cnt = 0; int arr[10]; void pal(int start, int end) { if (start == end || star..

문제 풀이 원소가 3개니까 원소가 {1개, 2개, 3개}인 부분 집합에 대해 각각 계산을 하면 된다. 원소가 3개라서 그냥 대충대충 작성했는데 원소가 이것보다 많아지면 백트래킹으로 원소를 뽑아서 계산하는 함수를 만들어야겠다. 평범하게 노가다 한 코드라 보는데 어려움은 없을 것이다. 소스코드 #include int main() { int arr[3]; int k, cnt = 0; for (int i = 0; i < 3; i++) scanf_s("%d", &arr[i]); scanf_s("%d", &k); for (int i = 0; i < 3; i++) { if (arr[i] == k) cnt++; } for (int i = 0; i < 2; i++) { for (int j = i + 1; j < 3; j..

문제 풀이 뭐 이딴 문제가 있지 싶었던 문제였다. 문자열로 받는 척하지만 전부다 int로 바꿔서 쓰고 출력도 좀 깔끔하지 못하다. 세상에 이런 문제가 있을 수도 있다는걸 깨닫기 위해 적는다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include int main() { char input; int y[2], m[2], d[2]; int index = 0, back; char s; while (true) { scanf("%c", &input); if (index

문제 풀이 반올림과 버림을 하는 문제이다. 그냥 원래 수에서 아래 2자리를 잘라두고, 잘라둔 수가 50이상이면 올려주고 아니면 그대로 두면 된다. 자릿수별로 숫자를 자르는 문제를 많이 풀었다면 어려움이 없을 것이다. 소스코드 #include int main() { int n; int arr[100]; scanf_s("%d", &n); for (int i = 0; i 4) printf("%d %d\n", arr[i] + 100, arr[i]); else ..

문제 풀이 어렵다. 큐를 이용하라는데 c++도 아닌 마당에 큐를 하나하나 구현하고 싶진 않아서 그냥 내맘대로 구현했다. 그리고 이게 더 편한 것 같다. 큐로 구현하려면 내가 쓴 논리 구조랑 아주 다른 방법으로 해야할 듯하다. factory 구조체를 만들었다. 이 구조체에는 공정별 소요 시간과 선행되어야 하는 공정이 있는지 있다면 그 선행 공정의 개수와 그 종류를 저장하고 마지막으로 해당 공정이 완료된 공정인지 확인하는 bool 변수를 넣었다. 먼저 공정별 소요 시간을 저장하며 선행 공정의 수인 b_num을 0으로 초기화 하고 isDone도 false로 초기화한다. 그리고 나서 선행공정의 관계를 입력받아 저장한다. 이 부분 코드가 좀 복잡해보일 수 있지만 어려운 부분은 아니다. 마지막으로 목표 공정 번호를..

문제 풀이 모든 경우의 수를 다 따져야 한다. 일단 P는 아무리 커봤자 N, M 중 작은 것보다 커질 수 없으니 N, M 중 작은 것을 찾는다. 이게 그 경우의 수들이다. 1. N이 P로 나누어 떨어짐 1. (M-2)가 P로 나누어 떨어짐 2. (M-1)이 P로 나누어 떨어짐 && (N-2)가 P로 나누어 떨어짐 2. (N-1)이 P로 나누어 떨어짐 1. (M-1)이 P로 나누어 떨어짐 2. (M-2)가 P로 나누어 떨어짐 && M이 P로 나누어 떨어짐 3. (N-2)가 P로 나누어 떨어짐 1. M이 P로 나누어 떨어짐 이걸 전부 떠올린다면 조건에 맞춰 코드를 작성하면 끝이니 쉽겠지만, 이걸 이렇게 전부 떠올리는게 힘들어서 문제다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #in..

문제 풀이 9개의 숫자 중 합쳐서 100이 되는 7개의 숫자를 찾는 문제이다. 달리 말하면 해당 숫자를 뺀 총합이 100이 되는 숫자 2개를 찾는 문제다. 일단 9개 숫자의 총합을 구하고 그 결과에서 100을 뺀다. 그 결과를 n이라고 치면, 이제 합쳐서 n이 되는 숫자 2개를 찾으면 된다. 숫자가 여러개였으면 백트래킹을 사용했겠지만, 2개라서 그냥 for loop 2개로 했다. 찾은 즉시 break로 빠져나오고 남은 수를 출력한다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include int main() { int arr[9]; int obj_num = 0; int x, y; for (int i = 0; i < 9; i++) { scanf("%d", &arr[i]); obj..