예외3 [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] 11724: 연결 요소의 개수 일단 이 문제도 결국 그래프 탐색 문제이다. 최단 거리와 관계가 없고 그냥 그래프가 서로 이어져 있냐만 확인하면 되므로 Depth-first(깊이 우선탐색)을 이용하여 인접행렬을 통해 문제를 풀었다. 여기서 유일하게 주의해야 할점은 노드가 하나라도 독립적인 연결 요소가 된다는 것이다. 그렇기 때문에 인접행렬에서 자기자신에게 가는 간선도 추가해줘야 간단히 풀 수 있다. #include int graph[1001][1001]; int visit[1001][1001]; void dfs(int n, int line, int x, int y) { for(int i=1;i 2023. 8. 6. 10250: ACM 호텔 #include #include int arr[26]; //알파벳마다 얼마나 많이 사용되었나! 일단 0으로 초기화 int main(void) { int n; scanf("%d",&n); for(int i=0;i 2023. 7. 8. 이전 1 다음