C30 [C/C++] 17626: Four Squares 일단 bruteforce하게 구현한 코드이다.(굳이 말하면 dp를 조금 이용하여 계산 수를 줄임) 먼저 제곱수는 최소 개수의 제곱수의 합이 1이므로 먼저 dp배열에 저장해준다. 최소개수의 제곱수의 합이 2인 수들은 최소 개수의 제곱수의 합이 1인 수 2개의 합이므로 MakeContinue 함수를 이용해 구하고 최소개수의 제곱수의 합이 3인 수들은 최소 개수의 제곱수의 합이 1인 수와 최소 개수의 제곱수의 합이 2인 수들의 합이므로 이를 이용해서 구하면 된다. 그리고 마지막으로 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으므로 dp[i]==0인 경우에 최소개수의 제곱수의 합이 4인것을 알 수 있다. #include #include int dp[100001]; //int tmp=cpy_o.. 2023. 8. 22. [C/C++] 9375: 패션왕 신해빈 이 문제는 의상의 이름은 중복되지 않기 때문에 의상의 종류가 몇개인지 세는것이 중요했다. strcmp를 이용해 기존의 저장되어 있던 의상이면 가장 처음 등장했던 의상의 종류의 index로 가 +1을 하고 새로운 의상이면 현재의 index에서 +1을 하였다. 이런 식으로 할 경우에는 cases 배열이 4 0 0 7 0 0 5 4 이런 식으로 될 수 있으므로 이를 4 6 5 4로 만들기 위해 함수 CopyCases를 이용하였다. int index=CopyCases(k); 그 후 입을 수 있는 의상의 경우의 수를 구하기 위해서 int result=CalculateCases(index);를 이용했다. 이때 경우의 수는 집합에서 공집합이 아닌 부분 집합을 세는 것과 같기 때문에 mult*=(cases_cpy[i].. 2023. 8. 22. [C] 11659: 구간 합 구하기 4 그냥 bruteforce하게 이중 for문을 이용해서 푼다면 시간초과가 나온다. 이때 구간 합을 이용하여야 하는데 i번째까지 합을 dp[i]에 저장하였다가 합을 구해야하는 구간에 대해서 result=dp[b]-dp[a-1]; 를 통해 구하면 된다. DP라고 보기에는 애매할 수도 있으나 중복되는 부분 문제를 줄일 수 있다는 점에서 의의가 있는 것 같다. 이건 꼭 알아야한다! 구간 합을 이용하면 시간복잡도를 n^2에서 n으로 획기적으로 줄일 수 있다! #include int arr[100001]; int dp[100001]; int main(void) { int n,m; scanf("%d %d",&n,&m); for(int i=1;i 2023. 8. 21. [C] 14940: 쉬운 최단거리 전형적인 BFS 문제로 각 목표지점까지의 거리를 출력하면 된다. 이때 각 거리를 저장하는 배열은 visit를 이용하였고 queue를 이용하여 bfs를 구현하였다. 주의해야할 점은 1.거리를 계산하기 위해 queue[2][] 부분을 거리를 위한 공간으로 할당하였고 queue[2][rear]=queue[2][front]+1; 를 통해 거리를 구할 수 있다. 2. 2가 있던 자리를 visit 배열에서 1로 할당했기 때문에 마지막에 출력하는 부분에서 0이 출력하도록 바꿔야한다. 이건 꼭 좀 잘하자! 맨날 풀었던 문제인데 bfs 구현하는데 이상한 곳에서 시간이 걸렸다. 특히 이번에는 front와 rear을 모두 1로 초기화해놓고 while문 들어가는 조건을 front 반복문 들어가는 조건과 다차원배열 index .. 2023. 8. 21. 이전 1 2 3 4 5 6 7 8 다음