해설35 [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] 1026: 보물 결국 함수 S를 최소화하기 위해 배열 A를 재배열 해야한다. 최소화 하기 위해서는 현재 남아있는 A배열에 가장 작은 수와 B배열에 남아있는 가장 큰 수를 곱해줘야지만 S의 값이 최소가 된다. 이 문제에서는 B에 있는 수를 재배열하면 안된다고 했지만 어차피 문제는 답만 맞으면 된다는 생각으로 A는 오름차순으로 B는 내림차순으로 정렬한뒤 같은 index끼리 곱해주었다. 사실 이 문제와 완전 같은 방식으로 하기 위해서는 이차원 배열 두 개를 만든 뒤 현재 남아있는 A배열에 가장 작은 수와 B배열에 남아있는 가장 큰 수를 곱해주고 그 수는 지나갔다는 표시를 남겨주어 다음번에 이 수는 아예 빼고 생각하도록 코드를 짜면 된다. #include int arrA[51]; int arrB[51]; void swap(in.. 2023. 8. 25. [C] 1929: 소수 구하기 사실 이 문제가 Dynamic Programming로 푸는 것은 아니다. DP는 점화식을 이용하여 i번째까지 구한 것을 저장하고 이것을 i+1번째를 구할 때 이용하는 것이다. 사실 이걸 그대로 사용하고 있지는 않다. 다만 DP에 쓰이는 방법 일부를 사용하고 있다. i번째 수가 소수인지를 각각 구하는 것이 아니라 1부터 탐색을 할때 소수이면 그 수의 배수들을 따로 저장하여 소수인지 확인하면 된다. 즉 Bottom-up 방식으로 생각해서 구현하면 된다. #include int dp[1000001]; int main(void) { int m,n; scanf("%d %d",&m,&n); for(int i=2;i=m && i 2023. 8. 10. [C] 1004: 어린 왕자 일단 문제는 예전에 원의 방정식에서 배웠던 것 처럼 출발점과 도착점이 각각 원 안의 있냐 없냐로 최소의 행성계 진입/이탈 횟수가 정해진다. 따라서 출발지/도착지와 원의 중점 사이의 거리가 원의 반지름보다 작다면 안에 있다는 것을 알 수 있다. 여기서 주의해야할 점은 출발점과 도착점이 모두 한 원 안에 있을 수 있다는 것이다. 그래서 한 원 안에 있는 경우의 수도 뺴줘야하기 때문에 tmp1과 tmp2를 이용해 출발점과 도착점이 각각 원안에 있는지 확인한 후 두개의 합, 즉 tmp1+tmp2==1인 경우에만 cnt++를 해줌으로써 문제를 풀었다. 기억해야할 점 1. pow 함수와 sqrt 함수는 모두 double형 변수에 대해서만 연산이 가능하고 다른 연산을 할때도, 예를 들어 나눌때, 계산결과가 달라질 수.. 2023. 8. 8. 이전 1 ··· 5 6 7 8 9 다음
