백준36 [C/C++] 2193: 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이 문제 역시 2차원 배열 dp[][]을 이용하여 풀었다. dp[i][0]에는 길이가 i인 이친수 중 0으로 끝나는 수의 개수를 dp[i][1]에는 길이가 i인 이친수 중 1로 끝나는 수의 개수를 dp[i][2]에는 길이가 i인 이친수의 개수를 저장하였다. 이렇게 나눈 이유는 마지막이 0으로 끝나면 그 다음에는 0과 1 모두 올 수 있지만 1로 끝나게 된다면 그 다음에 0밖에 못온다. .. 2023. 8. 31. [C/C++] 10844: 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 뜻하지 않게 이 문제를 11057: 오르막 수를 풀고 그 다음에 바로 풀었더니 굉장히 빨리 풀었다! 오르막 수에 관한 코드 설명은 아래 링크와 같다. https://donggul-godsang.tistory.com/66 [C/C++] 11057: 오르막 수 최대한 점화식을 구하려고 생각하다보니 규칙을 발견하게 됐다! 다른 DP 문제와는 다르게 2차원 배열을 이용하여 DP를 저장해야지 풀려서 생각하는데 조금 시간이 걸린 것 같다. dp[n][n]에서 첫번 donggul-godsang.tistory.com 이 문제.. 2023. 8. 30. [C/C++] 11057: 오르막 수 최대한 점화식을 구하려고 생각하다보니 규칙을 발견하게 됐다! 다른 DP 문제와는 다르게 2차원 배열을 이용하여 DP를 저장해야지 풀려서 생각하는데 조금 시간이 걸린 것 같다. dp[n][n]에서 첫번째부터 생각을 해보면 dp[1]=1 1 1 1 1 1 1 1 1 1 => 10 dp[2]=10 9 8 7 6 5 4 3 2 1 => 55 dp[3]=55 45 36 28 21 15 10 6 3 1 => 220 . . . 이런 식으로 나아가는데 dp[i]와 dp[i-1]간의 관계를 살펴보면 dp[i][1]=dp[i][10]이고 dp[i][2]=dp[i][1]-dp[i-1][1] dp[i][3]=dp[i][2]-dp[i-1][2] . . 이런 식으로 나아간다. 따라서 이렇게 쭉 뻗어나가면 점화식을 얻을 수 있다... 2023. 8. 30. [C] 2579: 계단 오르기 이 문제도 역시 배열에 저장을 해가며 점화식을 구하기 위해 노력하였다. 먼저 각 계단마다 점수를 저장하는 score배열을 정의하고 각 단계마다 가장 높은 점수를 저장하는 arr배열을 정의하였다. 그리고 초기, 계단을 2개 오르기까지의 경우는 for문이 아닌 직접 배열에 저장하는 방식을 택했고 (어떤 방법으로 for문을 구성할지 감을 잡기위해서 & 초기값은 직접 정해줘야함) for문에서는 연속된 3개가 되는지에 따라 if문을, 그리고 각각의 if문에서 2계단을 뛰어넘는게 이득인지 1계단을 뛰어넘는게 이득인지 판별해 arr배열에 저장하였다. 그리고 이때 이차원 배열을 이용한 이유는 연속된 3개의 계단을 오른지 판별하기 위해서였다. 소스코드는 아래와 같다. #include int main(void) { int.. 2023. 7. 22. 이전 1 2 3 4 5 6 7 8 9 다음
