백준 15992 1,2,3 더하기 7 이번에는 1,2,3 더하기 문제를 풀었다. 이 유형이 7문제나 있다는거에 놀랐다! 나 한개밖에 안해본거 같은데.. ㅎ 전에 풀었던 문제와의 차이점은 m 개의 숫자만을 사용하여야 한다는 점이 었다. 그래서 dp 배열을 만들어 점화식 dp[i][n] = dp[i-1][n-1] + dp[i-2][n-1] + dp[i-3][n-1] 을 세웠다. 이는 i 란 수를 만드는데에는, i-1 을 n-1 개의 (1,2,3)을 사용해 만든 경우와, i-2 를 n-1 개 사용해 만든 경우, i-3을 n-1개의 숫자를 사용해 만든 경우. 를 다 합치면 된다는 의미이다. 다 풀었는데 시간 초과가 나서 보니, 문제마다 dp를 할게 아니라, 1000x1000 사이즈에 대해 전부다 구하놓고 입력을..

백준 2502 떡 먹는 호랑이 오늘은 떡먹는 호랑이라는 문제를 풀어보았다. 사실 이 문제는 그냥 머리 굴려서 풀어보라고 하면 되게 쉬운 문제이다. 첫 날 준 떡을 a개, 둘째날 준 떡을 b개라고 했을 때 그 a,b 가 n번째 되는날 몇개씩 있는지 확인해 값을 대입해 찾기만 하면 되는데, 이 a,b 값이 뭔지 모르는 상태에서 더해가며 가져가는것 구현을 잘 생각을 해야 한다. 난 그래서 크기2 짜리 벡터를 만들어 a 와 b 의 개수를 저장하는 dp 를 만들었다. 그 후, i 를 1부터 i*a의 개수 값이 k 보다 작을 때까지 순회하며 만족하는 a,b 값을 찾으면 바로 리턴하도록 했다! for (int i = 3; i >d>>k; dp[1][0] = 1; //각각 a, b 의 개수 의미 dp[1][1] = 0..

백준 4883 삼각 그래프 오늘은 삼각 그래프 문제를 풀었다. DP 를 이용하면 풀 수 있겠다는 감이 바로 왔는데, 그래프를 내가 제대로 봤으면 쉽게 해결했을 것 같은데 그러지 않아서 오래 걸렸다. 또 신경 써야하는 문제점도 있었기 때문에 여러번 틀리고 나서야 답을 구할 수 있었다. 먼저, 그래프의 화살표가 어디로 향하는지 잘 봐야한다. 그 다음, 왼쪽 제일 위의 값을 신경을 써줘야 한다. for (int i = 1; i

백준 10942 팰린드롬? 이번 문제는 DP 를 활용해야 하는 문제였는데, 분명 dp 란 것을 알고 있었음에도 어떻게 메모이제이션 해야할 지 감이 오지 않았고, 답을 참고해서 풀었다. 담에 이런 문제 나오면 무조건 스스로 해내야지! i ~ j 까지의 범위가 팰린드롬인지 알기 위해선 i+1 ~ j-1 까지의 범위가 팰린드롬인지 부터 아는 것이 당연하다. 만약 i+1 ~ j-1 까지 팰린드롬이고 i 와 j 번째 의 수가 같다면, 당연 i~j 까지는 팰린드롬인 것이다. 이제 이 당연한 사실을 코드로 짜기만 하면 되는데, 그게 생각처럼 쉽지가 않다 하하하하 for (int i = 2; i

백준 10826 피보나치 수 4 이번 문제는 피보나치수를 구하는 간단한 문제였는데, c++ 에서 가장 큰 수 의 범위를 그냥 넘겨버려서 unsigned long 을 한다고 해결되는 문제가 아니었다.ㅜ 다른 언어는 상관이 없나 레벨이 엄청 낮았는데, 실버 5를 받을 만큼 쉬운 문제는 분명 아니다! 이 문제를 해결하기 위해 문자열로 입력을 받아 더하는 방식을 구현해야 했다. string string_add(string x, string y) { int num; int carry = 0; string result; reverse(x.begin(), x.end()); reverse(y.begin(), y.end()); while (x.length() < y.length()) { x += &#39;0&#39;; ..

백준 16400 소수화폐 오늘은 소수화폐 문제를 풀었는데, 에라토스테네스를 이용해 소수를 구한 후 이를 이용해 dp 문제를 풀면 되었다. 동전 dp 문제를 오랜만에 풀었더니 기억이 잘 안나서 시간이 오래걸렸다. (알고리즘 문제 자체가 좀 오랜만인것 같기도 하고...) 우선 에라토스테네스로 소수를 구하는 방법이다. for (int i = 0; i