NUMB3RS

알고리즘/algospot 2015. 2. 21. 12:15 Posted by 아는 개발자

동적 계획법을 이용하면 풀기 편하다.

d[마을수][지난날수]로 자료형을 잡고

if(connected[현위치][마을])

d[현위치][날짜] += d[마을][날짜-1]/deg[마을]로

구할 수 있다.

그런데 제출하면 왜 틀리다고 나오는지 모르겠다;

책에있는데로 그대로 따라하는데... 

알고스팟 뭔가 좀 이상하다.... 물론 나한테 문제가 있는거지만 ㅠ

728x90

'알고리즘 > algospot' 카테고리의 다른 글

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

2631

알고리즘/acmicpc 2015. 2. 17. 19:13 Posted by 아는 개발자

알고리즘 문제들은 서로 다른 문제 같아도 같은 개념을 사용하고 있음을 이해하면

문제풀기가 편하다.

줄세우기문제는 앞으로 옮기고 뒤로 옮기고 해서 어려워 보이지

사실은 증가하는 순열중 가장 긴 순열을 찾으라는 문제와 같다.

옮기는 횟수는 전체 배열의 크기에서 증가하는 순열중 가장 긴 순열의 개수를 뺀 것과 같다.

아.. 이렇게 빠르게 이해됫으면 얼마나 좋을까

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17

1958

알고리즘/acmicpc 2015. 2. 17. 18:38 Posted by 아는 개발자

세개의 문자에 대해서 LCS를 찾는것

d[][][] 3차원배열을 만들고 점화식은 같다

사실 공간에 취약해서 왜 이렇게 답이되는지 증명하라면 좀 시간 걸릴것 같다

하지만 LCS 문제를 푸는데 착안해서 풀었다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15

9252

알고리즘/acmicpc 2015. 2. 17. 18:09 Posted by 아는 개발자

LCS 살짝 변형한 문제다

문자열에대한 dp[][]배열을 만들어주면 된다.


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15

9251

알고리즘/acmicpc 2015. 2. 17. 17:18 Posted by 아는 개발자

LCS문제

모두의 부부수열이 되는 수열중 가장긴것을 찾는문제

전형적인 dp문제인데 이때 d배열을 2차원으로 해야한다는 점이 중요

점화식만 잘 만들면 어렵지 않게 해결 할 수 있다.

현재 위치의 dp값을 지정해주려면


if(A[i] == B[i]) dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])

else dp[i][j] = max(dp[i][j-1], dp[i-1][j])


요렇게

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14