[백준] 1932번 정수 삼각형

역시나 점화식을 짜놓고, 오류 고친다고 오히려 시간을 더 사용한 문제다...일단 점화식을 짜보자 경로는 무조껀 왼쪽 대각선 혹은 오른쪽 대각선이다. 그렇담 7에서 나가는 3 과 8을 경로로 잡는다고 하면, 7->3(10), 7->8(15) 이다.가운데의 1에 갈 수 있는 방법은 7->3->1 또는 7->8->1 그러나 7->8->1 이 더 크기 때문에 7->3->1 은 무시한다.또한 또하나의 법칙이 있는데, 좌측 제일 하단의 4와 우측 제일 하단의 5가 보이는가?저 길까지 가는 방법은 무조건 첫번째 배열에서 좌측 대각선으로 가거나, 우측 대각선으로 가는 방법밖엔 없다.예) 7에서부터 시작해서 좌측 하단의 4까지 거리를 만드는 방법은7->3->8->2->4 순으로 가는 방법밖엔 없다.우측 또한 마찬가지다...
알고리즘/동적계획법 6년 전

[백준] 1149번 RGB거리

이것도 하나하나 탐색해가며 찾으면 될 것같다. 저번 타일링 문제 처럼 말이다.일단 점화식부터 세워야 하는데 기본적으로 모든 값중 최솟값을 찾는 점화식부터 세워보자N이 0일땐, 아무것도 채워넣을 수 없다. 그러므로 dp[0]은 0,일단 예제에서 N 이 1일땐, 0번째는 26 1번째는 40 2번째는 83이다. 이중 최솟값은 26이니 dp[1]는 26,N이 2일땐 0번째는 49 1번째는 60 2번째는 57이다. 이중 최솟값은 49이니 dp[2]는 dp[1]까지 합친 값인 75그럼 점화식은 결국 dp[i] = dp[i-1] + arr[i]; 이다. (arr[i] 는 현재 N값중 가장 작은 값이다.) 이제 제약조건인 이웃이 이미 칠한 색깔은 칠 할 수 없다 를 풀어보자일단 arr와 dp를 모두 2차원 배열로 설정..
알고리즘/동적계획법 6년 전

[백준] 11727번 2 x n 타일링 2

https://openmynotepad.tistory.com/6 저번 11726번 문제에서 2x2 타일이 하나 더 생겼다.저번 문제랑 바뀔 점이 없는것이, 이미 2x1 타일과 1x2 타일로 채운 방법을 짜봤고,2x1 타일은 2x2과 같은 N을 가지므로, 점화식은 N = (N-1) + (N-2) + (N-2) 가 된다. ( 1x2 타일로 시작해서 채우는 방법 + 2x1 타일로 시작해서 채우는 방법 + 2x2 타일로 시작해서 채우는 방법) 2xn타일링 소스에서 full(n-2)를 한번 더 더해주면 된다.
알고리즘/동적계획법 6년 전

[백준] 11726번 2 x n 타일링

누군가에겐 쉽겠지만 이제 공부하는 나한테는 생각하는데 30분 정도 걸린 문제다..만약 N이 1이라면 1x2 타일 하나밖에 쓸수 없으니 1이다.N이 2라면 ? 1x2 타일 2개를 쓰는 방법 하나, 2x1 타일 1개를 쓰는 방법 하나. 2이다. 결국엔 N의 크기에 따라 뭘로 채울꺼냐는건데, 1x2로 채우는 방법, 2x1로 채우는 방법을 다 구해보면 될 것 같다.(N-1) + (N-2) = 방법N이 예를 들어 3이라면, 1x2 타일로 하나를 채우고(N-1)2로 들어간다, 2에선 또 1x2 타일로 하나를 채우고(N-1)1로 들어간다. 1에선 1x2 타일 하나밖에 채울수 없으니 방법 1개 완료2로 돌아온다. 1x2 타일로 채우는 방법은 다 해봤으니 2x1 타일로 채우는 방법으로 돌아간다.현재 가로 공간은 2가 남..
알고리즘/동적계획법 6년 전

[백준] 2579번 계단 오르기

벌써부터 귀찮다. 점화식부터 세워보자 을 예시로 들고 3번째 계단까지 올라가며, 최대 점수를 구한다고 하면 ( N = 3 )두가지 방법이 있다1 번째 계단을 밟고 3 번째 계단을 밟기 ( 10 + 15 )2 번째 계단을 밟고 3 번째 계단을 밟기 ( 20 + 15 )둘 중 더 높은 점수를 구해야 하니 3번째 계단의 최대 점수는 354 번째 계단까지 올라가며, 최대 점수를 구한다고 하면 ( N = 4 )1 번째 계단을 밟고, 2 번째 계단을 밟고, 4 번째 계단을 밟기 ( 10 + 20 + 25 )1 번째 계단을 밟고, 3 번째 계단을 밟고, 4 번째 계단을 밟기 ( 10 + 15 + 25 )2 번째 계단을 밟고, 4 번째 계단을 밟기 ( 20 + 25 )4 번째 계단의 최대 점수는 55 결국 N번째 계단..
알고리즘/동적계획법 6년 전

[백준] 1003번 피보나치 함수

fibonacci (이하 F) 는 F(0)일땐 0이 1 번 호출 , F(1)일땐 1이 한번 호출 된다고 했다..그럼 F(2)는? 피보나치는 F(n-2) + F(n-1) 의 점화식을 가지고 있으니 0이 1번 호출, 1이 한번 호출 될 것이다. 그럼 이것을 소스로 풀이해보면... 사실 배열을 통해서 만들어도 되는데, 누구한테 보여줄 소스도 아니고 내가 보고 편하게 하기 위해서 vector>를 사용했다.사실 최대 입력하는 갯수가 40개 이하라고 했으니, reserve 로 40까지 잡아줬어야했는데 내 불찰인것 같다. 나중에 수정하자. 벡터가 첨자연산([])을 지원하니, vt[0] 일땐, F(0)과 같다고 보면 된다. 즉 vt[0].first = 1, vt[0].second = 0 ( first는 return 0..
알고리즘/동적계획법 6년 전