줌코딩의 코딩일기

문제 문제 링크 문제 접근 이전 LCS를 점화식을 이용해서 풀었다면 이 문제는 그리 어려운 문제가 아니다. 점화식의 경우의 수를 나눠보자. 먼저 각 문자열의 해당하는 변수(x, y, z)가 문자열 끝에 다달았을 때는 0을 반환한다. 그리고 이미 dp값이 정해진 길을 갈 때면 그 dp값을 반환한다. a[x] = b[y] = c[z]라면 1을 더하고...

문제 문제 링크 문제 접근 그렇게 힘들게 풀던 것을 점화식을 이용하니 엄청나게 수월하게 풀려버렸다. 점화식을 이용해서 a[i]와 b[j]가 같은 경우에만 점수를 더한다. 같지 않다면 x를 키우는 길과 y를 키우는 길, 두개로 나눠서 점화식을 이어간다. 이 때 이미 값을 구해본 길을 가게 된다면 그 값을 이용하고 더 나아가지 않는다! LCS 문자열...

문제 이 문제는 점화식으로 풀면 너무 좋은 문제이지만, 그렇게 풀지 않는다면 정말 고통속에서 코드를 짜게 될 수도 있다. 문제 링크 문제 접근 처음에 이문제를 평소 푸는 것 처럼 점화식을 이용하지 않고 풀려고 했다. 하지만 이와 같이 규칙이 딱딱 정해져 있는 경우에는 점화식을 이용하는 것이 훨씬 수월하다는 것을 나중가서 깨달았다. 일단...

문제 문제 링크 문제 접근 이 문제는 처음부터 각 수를 기준으로 해서 팰린드롬을 만들고 각 위치까지 올 수 있는 최소 개수를 업데이트한다. 코드 #include <cstdio> char s[2501]; int i, dp[2501], x, y, pre; int main(){ scanf("%s", s); for(int i = 0; i < 2501; i++)dp[i] = 2500; for(i = 0;...

문제 이 문제는 경우의 수를 구하기 위해 조합론을 알면 좋다. 문제 링크 문제 접근 각 자리에 a가 올 경우에 가능한 경우의 수를 세고 k가 그 안에 들어가면 그 자리에 a를 넣고 아니면 z를 넣고 k에서 a가 올 때의 경우의 수를 빼준다. 다음 자리에도 위의 과정을 반복한다. 이때 경우의 수는 조합을...