EQ1의 짱무말 갓잔치 EQ1의 짱무말 갓잔치

사실 함수를 새로 만들어서 재귀처럼 풀 필요도 없이 그냥 3중 for문으로 풀어도 되긴하지만 이렇게 함수로 기능을 분리하는 것이 내가 읽기도 쉽고 내 취향이라서 이렇게 풀었다. count(n, k)라는 함수는 k개의 숫자로 n을 만드는 경우의 수를 출력해주는 함수다. 그렇다면 어떻게 점화식을 세울 것인가? 나는 k를 기준으로 점화식을 세웠다. n을 만들기 위해 마지막으로 더한 숫자가 0이라면? 그 전까지는 k-1개의 숫자로 n을 만든다 = count(n, k-1) n을 만들기 위해 마지막으로 더한 숫자가 1이라면? 그 전까지는 k-1개의 숫자로 n-1을 만든다 = count(n-1, k-1) (생략) n을 만들기 위해 마지막으로 더한 숫자가 n-1이라면? 그 전까지는 k-1개의 숫자로 1을 만든다 = c..

처음에는 최단거리이면서 내리막길을 구하는 것인줄 알고 쉽네?! 하면서 했서 틀렸다... ㅋㅋ 문제를 잘 읽도록 하자. 단순 DFS만 적용하면 타임아웃이 날게 뻔하기 때문에 DP를 이용해 기록해두면 된다. 일단 DFS로 설명하면 (0, 0)에서 (x, y)로 가는 경로의 수를 count(x, y)라고 하자. (x, y)로 올 수 있는 경로는 다음 4가지이다. 하지만 이 4 장소가 모두 유효한 장소는 아니다. 이들에 대해 2가지 조건이 붙는다. 지도에 존재하는 장소일 것 (x, y)보다 값이 클 것 (같아서도 안된다!) 만약 위 두 조건을 모두 만족하는 위치가 (x - 1, y)와 (x, y + 1)이였다면 count(x ,y)는 다음과 같다. 순수 DFS로는 이렇게 되지만 매번 count함수를 통해 값을 ..

음.... 이거 이렇게 풀어도 되는걸까? 싶은 문제였다. 당연히 시간 초과를 예상하고 제출했는데 왠걸? 그냥 통과됐다. ??? 뭐지? 만우절 장난인가? 진짜 별거없이 O(NMK)의 알고리즘으로 돌렸다. 하나 힘들었던 것은 문제에서 i, j, x, y를 이미 사용하고 있어서 for문 돌릴 때 다른 문자를 사용해야 했다는 점.... ㅋㅋㅋ #include #include using namespace std; int n, m; int arr[300][300]; int sum(int i, int j, int x, int y) { int total = 0; for(int a = 0; a < n; a++) { for(int b = 0; b < m; b++) { if(i m; for(int i = 0; i < n; ..

예전에 LIS 공부를 조금 해놓아서 그래도 금방 풀었다. 핵심 개념은 결국에 이거다. 첫번째 수열부터 쭈우욱 돌면서 i번째 항이 되었을 때! i번째 항이 말한다. for(int i = 0; i seq[j]) "너를 포함한 가장 큰 증가 부분 수열의 합에다가 나를 더하면 내가 현재 가지고 있는 합보다 크냐?!" max 함수를 통해 크면 가지고 아니면 버린다. sum[i] = max(sum[i], sum[j] + seq[i]); 그걸 반복한다. 그리고 마지막으로 ..

원래 백준의 단계별 문제의 [분할정복]을 다 풀려고 했는데 뒤 쪽 문제가 너무 어려워서 포기하고 알고리즘 분류에서 [다이나믹 프로그래밍] 시리즈를 풀기로 했다. 기존의 냅색 문제와 비슷하다. 모든 수는 1을 자기 자신만큼 더해서 표현할 수 있으므로 termCnt[i] = i를 기본으로 둔다. 이후 for문을 통해 j * j를 빼가면서 할당되어 있는 termCnt[i] 와 termCnt[i - j * j] + 1 중 작은 값을 termCnt[i]에 할당한다. termCnt[i - j * j] + 1에서 1을 더한 이유는 j * j가 하나의 항을 차지했기 때문이다. #include #include using namespace std; int termCnt[100004]; int main() { int n; ..

풀고 나서 허무했다. 너무 어렵게 생각한 것 같다. 되게 뭐가 있을 것처럼 설명해놨잖아! 그래서 막 m이 2의 제곱수인지 5의 제곱수인지 등등을 파악해서 경우의 수를 나눠서 구해야 하는 줄 알았다.... 하지만 그냥 Brute Force 였구요~~ do - while 문을 실제 문제에서 한 번 사용해봤다는 점에서 조금 유익하긴 했다. 풀이 방법은 결국 주기만 구하면 되는 것이기 때문에 첫 항과 두번째 항을 설정하고 while 문을 돌려서 첫째 둘째항과 동일한 항이 나올 때까지 count를 증가시킨다. 동일한 항이 나오면 그 때 count가 곧 주기이므로 그 값을 리턴한다. #include #include using namespace std; int p; int fisano(int div) { int fi..

분할 정복 시리즈의 4번째 문제다. 사실 분할 정복...보다는 그냥 수학문제에 가깝지 않나 싶다. 일단 기본 개념은 다음과 같다. 이 식은 x를 y로 나눈 나머지라는 뜻이다. 나머지를 티스토리 수식으로 어떻게 쳐야할지 몰라서...ㅠㅠ 이 수식에 대한 증명은 시간이 남으면 그때 추가로 달 생각이다. 아무튼 이 문제의 요지는 어떻게 큰 숫자들을 잘 관리할 것인가 + 재귀로 진행했을 때 지수의 값이 클수록 엄청난 메모리가 소비되는데 이것을 어떻게 할 것이냐 이다. 문제에서 b가 21억으로 주어질 수도 있기 때문에 단순한 brute force로는 할 수 없다. 따라서 절반으로 나눠가면서 진행했다. 또한 최초에 a를 그냥 넣지 않고 한 번 c로 나눈 나머지로 바꿔줘야 한다. 기본 연산자는 메모리나 연산 속도에 전..

백준 2630번 : 색종이 만들기 문제의 상위 버전....이라고 하기에도 약간 부끄러운 그냥 숫자만 바꾼 문제다. 그래서 2630번의 풀이 방법을 그대로 이용했다. (2630번 풀이 : https://stillchobo.tistory.com/72) 다른 점이라면 4등분 하던 것을 9등분 했을 뿐! 그래서 설정한 영역에서 하나라도 다른 것이 발견되면 영역과 범위를 새로 지정한 함수를 9번 불러준다. 사실 이렇게 무식하게 해도 되나 싶긴하다. check 함수를 9번이나 부르다니....ㅋㅋㅋ 하지만 굳이 저걸 이중 for문을 이용해서 적는 것도 실수할 구석이 많으니까 그냥 9번 쌩으로 적었다. #include #include using namespace std; int n; int arr[2187][2187]..