문제
접근 방법
대칭을 이루는 경우는 무엇이 있을까?
1, 2, 3으로 이루어진 조합이라면 여러 가지 있을 것이다.
예제에서 준 정수 4의 경우도 1+2+1, 2+2, 1+1+1+1가 있다.
2의 경우를 살펴보자. 1+1, 2위의 식과 유사한 것을 볼 수 있다.
6의 경우는 어떻게 될까?
1*6, 1+2+2+1, 1+1+2+1+1, 2+1+1+2, 2+2+2, 3+3
양옆에 1 또는 2가 붙은 모양새이다. 4의 경우는 2+2, 6의 경우에는 3+3이라는 예외가 발생하지만 3+3을 마지막으로 예외가 발생할 일은 없을 것이다. (3+3 또한 0에 양옆에 3을 붙인 모양이다. 하지만 3이 사용할 수 있는 수에서 가장 큰 값이므로 더 이상 발생할 일이 없다고 말한 것이다)
그렇다면 1~6까지의 경우를 확인해주고 양옆에 1, 2, 3을 붙여주는 방식으로 해결하면 된다는 결론이 나온다.
코드
#include <iostream>
using namespace std;
long long dp[100001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
dp[1] = 1; // 1
dp[2] = 2; // 1+1 2
dp[3] = 2; // 1+1+1 3
dp[4] = 3; // 1*4 2+2 1+2+1;
dp[5] = 3; // 1*5 2+1+2 1+3+1;
dp[6] = 6; // 1*6 1+2+2+1 1+1+2+1+1 2+1+1+2 2+2+2 3+3
int T, min = 7;
cin >> T;
while (T--)
{
int n;
cin >> n;
for (int i = min; i <= n; ++i)
{
dp[i] = (dp[i - 2] + dp[i - 4] + dp[i - 6]) % 1000000009; // 양쪽에 1, 2, 3을 붙인다.
}
cout << dp[n] << "\n";
if (n > min)
min = n;
}
return 0;
}풀이
2, 4, 6만큼 떨어진 곳에서 값을 가져와서 합산하면 된다.
min이라는 변수까지 잘해놓고는 n과 비교하여 갱신하는 것을 하지 않아서 시간 단축을 못 했다.
다른 사람은 0ms인데 나 혼자 320ms이길래 뭔가 싶어서 둘러보다 알게 됐다. 이런 사소한 부분에서 실수하는 걸 조심해야겠다.
또한 0에 양옆에 2, 3을 더하면 2+2, 3+3이 된다는 점에서 식을 적용할 수 있을 것 같은데 (dp[0]=1을 이용하면 될 것 같았다) 귀찮아서 안 했다. 실제로 계산해보면 맞아떨어진다. 하지만 dp[i-6]에 대한 처리를 해야 하기에 귀찮아서 그대로 두었다. (4의 경우에는 i-6의 인덱스는 존재하지 않으니 반복문안에 넣으려면 조건문을 걸던지 해야 한다)
