전체 글102 [C] 21736: 헌내기는 친구가 필요해 간단하게 풀 수 있는 문제였다. X가 벽이고 O로 지나갈 수 있으며 P를 만날때 people++을 해주면 된다. 그리고 결국 그래프를 순회만 하면 되기 때문에 Depth-first를 이용해 풀어주었다 #include #include char graph[601][601]; int visit[601][601]; int people=0; int x_coordinate[4]={0,0,1,-1}; int y_coordinate[4]={1,-1,0,0}; void dfs(int x,int y,int x_max,int y_max) { for(int i=0;i 2023. 8. 23. [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. 이전 1 ··· 10 11 12 13 14 15 16 ··· 26 다음