BOJ 그리디 문제 모음2/C++/30(#10610)/병든나이트(#1783)/NMK(#1201)

모두 C++로 작성하였음을 유의하자. 

1. 30 (#10610)

https://www.acmicpc.net/problem/10610

30 = 3 * 10 이다. 3과 동시에 10으로도 나누어 떨어져야 하므로, 우선 0이 하나 들어가야하고, 0을 제외한 나머지 숫자들의 합이 3의 배수가 되어야 30의 배수도 동시에 만족할 수 있다. 나는 먼저 string 을 순회하면서, 0이 있을때마다 카운트 해서 zeros 에 저장했고, 각 자리수의 합을 check에 더해나가는 방식으로 마킹했다. -> 이후 zeros 가 0 이거나 check이 3으로 나눠떨어지지 않는 경우는 예외처리를 해줬다. 

다만, 주의할 점은 받을 N이 10^5개의 숫자로 구성되있다는 점이다. 즉, 자리수가 nnnnnn...........nnnn (10^5개) 를 의미하므로 기본 int형은 감당할 수 없는 자료구조다. 따라서 string으로 그대로 받아서 string으로 출력해주는 스킬이 필요하다. 이 점 꼭 유의하자. 

Source Code:  https://github.com/brwnsugr/algorithm/blob/master/boj/10610_30.cpp

2. 병든 나이트(#1783)

https://www.acmicpc.net/problem/1783

높이인 N 값이 1 인경우, 2인 경우, 3인경우를 나눠서 생각해보자. 

Source Code: https://github.com/brwnsugr/algorithm/blob/master/boj/1783_sick_knight.cpp

3. NMK(#1201)

• 우선 감소하는 최장 수열의 길이인 K를 먼저 고려해서 최소의 값인 K부터 시작하는 K, K-1, .... , 1 을 배치하고,
• 이 뒤에 M을 고려해서 바로 증가하는 최장 수열을 넣는다.
• 이 과정에서 최장 수열의 규칙은 최장 수열의 마지막 부분은 가장 큰 값인 N이 되도록 한다. 
• 감소하는 최장 수열, 증가하는 최장 수열을 나열한 이후 나머지에 대해서는 최장 수열의 마지막 부분인 N 이후에 나열하게 되는데, 이때 사용하지 않은 나머지 숫자 중, 가장 작은 숫자를 먼저 배치, 그 다음엔 남은 숫자 중 가장 큰 숫자 배치, 그 다음은 남은 숫자 중 가장 작은 숫자 배치, ..... 이런식으로 지그재그로 진동시켜서 이후에 나타는 감소 최장 수열, 증가 최장 수열을 최소값(2)로 계속 유지해준다. 

Source Code: https://github.com/brwnsugr/algorithm/blob/master/boj/1201_NMK.cpp