김쿠쿠:커밋은했니!

1. 문제 algospot.com/judge/problem/read/DRAGON 2. 필요한 개념 - 동적계획법 : 동적 계획법이란 앞의 사건이 뒤의사건에 영향을 미쳐 앞의 것을 저장해놓고 뒤에 사건을 계산할 때 꺼내 쓰는 것이다 . 이 문제에서는 앞의 X 가 뒤의 X+YF 가 되고 앞의 Y 가 뒤의 FX -Y 가 된다. 따라서 앞의 사건이 규칙적으로 이루어지며 뒤의 사건에 영향을 주기때문에 다이나믹 프로그래밍으로 풀어야 된다. 3. 내 전략 우선 처음에는 쉽게 생각했다ㅎㅎ /... P가 1,000,000,000개까지 인것을 보기 전까지... 그냥 단순하게 규칙을 보니 FX와 YF 만 달라지고 중간에 +- 만 계속 달라지길래 +-를 STRING에 저장하는 전략을 사용하였다. 두번째로 앞의 사건이 그대로 ..

1. 필요한 개념 - dfs 란(뇌피셜 정리.. ) : 재귀를 통해 전체 경우를 다 보는 탐색을 말한다 > 이때 전체 경우를 다보는 경우도 있고, 경우를 찾으면 멈추는 경우도 있음! - 백트래킹 백트래킹이란 dfs에서 뒤에서부터 모든 순열을 다 조합하는 것이다. (주로 내가 이럴 때 쓰는데 정의가 이것은 아니다..) 2. 문제 3. 풀이 부분 수열이란 한 수열에서 특정 숫자를 골라서 만든 수열이다. 즉 특정 숫자가 들어가고/안 들어가고 두 가지의 경우로 나뉜다. (고등학교 때 부분수열의 개수가 공집합 포함해서 2^N개인 거 배웠죠,, 그런 개념) 그래서 나는 dfs(int 인덱스, int 합)인 함수를 만들고 - 해당 인덱스의 숫자가 들어가는 경우 : sum = sum + arr [i] // arr은 원..

1. 필요한 개념 - 동적계획법(뇌피셜로 작성하였음.. ) 동적계획법은 뒤의 사건이 앞의 사건에 영향을 받을때 이용된다 그래서 동적계획법 문제는 점화식으로 풀리는 문제가 많다.. 2. 문제 3. 풀이 문제가 복잡해 보이지만 따지고 보면 1. 앞에서부터 봤을때 증가하는 수열 + 2. 뒤에서부터 봤을때 증가하는 수열 ---------------------------------------- =앞에서부터는 증가하고 뒤로는 감소하는 수열 을 찾을 수 있는 원리이다. 그래서 나는 앞에서 부터 증가하는 수열을 Icache에 담고 뒤에서부터 증가하는 수열을 Dcache에 담은 후 각 인덱스 마다 Answer = Max(Icache + Dcache)를 했다. 4. 코드 #include #include #include u..