[일반] C번 시간초과 질문 ...

[익명(123.109)]

일케 짰는데 시간초과나더라구...

40000짜리 2초에 안돌아가는데 어캐 더 줄임??

팔린드롬 498개 다 구하고 합을 구성하는 젤 작은 팔린드롬의 인덱스를 s, 만드려는 수를 x로 주고

dp 를 돌렸음 다른방식으로 해야함?

[익명(221.167)]

4만 짜리를 2차원으로 어떻게 돌리냐;; 난 이 부분부터 식겁했음 어떻게 해야 할지 모르겠어

[익명(123.109)]

난 500 * 40000 이라서 돌아가긴했음 ㅇㅅㅇ

[익명(123.109)]

하나는 팔린드롬 인덱스 줬어 근데 시간초과남...

[익명(221.167)]

500가 왜?

[익명(221.167)]

팰린드롬 수를 1부터 4만까지 다 찾아봄?

[익명(123.109)]

ㅇㅇ 내컴에선 150ms 정도 밖에 안걸리던데

[익명(221.167)]

그럼 팰린드롬 수를 가지고 어떻게 활용함? 해답이 팰린드롬 밖에 안 보이는데

[익명(123.109)]

그 dp점화식을 dp[s,x] = 최소팰린드롬이 s이면서 x를 만드는 방법의 수. 이렇게 품. 그럼 s는 숫자 말고 팰린드롬 인덱스를 쓸 수 있음.

[익명(221.167)]

그럼 됐네 시 ㅡ발

[익명(123.109)]

ㄴㄴ 시간초과남... 전 글 댓처럼 1차원으로 풀어야하는 듯 ㅋㅋ

[익명(118.41)]

매번 솔브하지 말고 저장해뒀다가 돌려도 안 돌아감? 코드는 안 읽긴 했는데 충분히 될 거 같은데

[익명(123.109)]

ㅇㅇ ret -1 넣고 dp한거임

[익명(118.41)]

ac로 증명해온다

[익명(123.109)]

ㅋㅋ 저 코드 TLE on pretest 3임

[익명(123.109)]

바텀업은 될지도...

[익명(123.109)]

바텀업 1차원 dp로 하면 풀리네... 신기하다 이거

[익명(123.109)]

dp[0]=1; for (int p : ps) for (int x=0; x<=40000-p; ++x) dp[x+p] = dp[x]; 일케하니깐 되네

[익명(123.109)]

최소 palindrom 을 s로 하면 안되고 최대 팰린드롬을 정해서 해야하네