C30 [C] 2293: 동전 1 시간이 엄청 오래걸려서 풀었다.. 일단 맨 처음에는 재귀함수를 이용한 Top-Down 방식으로 풀려고 노력했는데 예외처리를 해줘도 지수적으로 증가하기 때문에 자꾸 시간초과가 났다. 여기서 주의해야할 점은 각각의 코인의 가치에 따라서 dp를 따로 생각해야한다는 점이다. 결국 마지막에는 하나로 모아 풀어야하지만 처음에 생각은 따로따로 해야한다는 점인데 그 결과 구현을 하자면 dp[i]+=dp[i-price[j]]; 가 된다 1. j번째 동전을 포함하지 않은 상태에서 i의 가치를 표현하기 위해서는 j-1번쨰 동전까지만을 이용하여 만들 수 있는 경우의 수를 구하면 되기 때문에 dp[i]+=dp[i]...가 된다. 2. j번째 동전을 포함한 상태라는 뜻은 결국 가치가 i-price[j]가 되는 경우의 수를 구하면.. 2023. 8. 21. [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. [C] 9663: N-Queen 구현은 다음과 같이 진행했다. 1. 퀸이 놓이면 퀸이 공격할 수 있는 자리들에 chess배열에 1을 추가하여(색칠하여) 저장하였다. 1-1.이때 가로 세로는 그냥 칠하고 (겹치는거 빼줌), 대각선을 색칠할 때는 while문을 이용하여 색칠해줬다. 이때 색칠하는 방법은 전에 풀었던 "토마토"문제와 같이 미리 x,y좌표로 갈 수 있는 경우의 수를 배열로 저장하고 (x,y_coordinate) for문을 이용해 구현했다. 1-2 이때 그래프의 범위를 벗어나면 for문을 빠져나오도록 했다 2. 이후 빈 공간에 queen을 배치할 수 있는지 판단하고 배치 가능하면 color함수를 재귀적으로 호출한다. 2-1. 이때 계속 덧칠하면서 color을 호출했기 때문에 호출 후 return하면 다시 지워주기 위한 remov.. 2023. 8. 6. 이전 1 ··· 3 4 5 6 7 8 다음