구현6 [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] 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. [C] 2292: 벌집 계차수열을 이용하여 수식을 구해서 풀 수 있다 거리가 1인 벌집은 1 거리가 2인 벌집은 2~7 거리가 3인 벌집은 8~19 거리가 4인 벌집은 20~37.. 이런 식으로 진행되기 때문에 거리가 n일때 벌집은 f(n-1)~f(n)까지 일 것이다 맨 끝 벌집이 1->7->19->37->61..로 증가하고 각 끝 벌집끼리는 6->12->18->...로 증가하는 것을 알 수 있다. 따라서 계차수열을 이용하면 f(n)=3*n^2-3*n+1인 것을 알 수 있다. 이를 이용해 문제를 풀게 되면 아래와 같다. #include int main(void) { int n; scanf("%d",&n); int i; for(i=1;i7->19->37..) if(k>=n) //입력받은 수가 거리보다 작을때 멈춤 break; }.. 2023. 7. 8. [C] 2908: 상수 이 문제는 여러가지 풀이가 가능하지만 입력 조건이 매우 간단하기 때문에 밑에 소스코드처럼 작성하면 쉽게 풀 수 있다. #include int main(void) { int a,b; scanf("%d %d",&a,&b); int x,y,z; z=a%10; //일의 자리수 y=(a/10)%10; //십의 자리수 x=(a/100)%10; //백의 자리수 int result1= z*100+y*10+x; z=a%10; //일의 자리수 y=(a/10)%10; //십의 자리수 x=(a/100)%10; //백의 자리수 int result2= z*100+y*10+x; if(result1>result2) printf("%d",result1); else printf("%d",result2); return 0; } 다만, 좀.. 2023. 7. 8. 이전 1 2 다음