알고리즘!76 [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] 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 ··· 7 8 9 10 11 12 13 ··· 19 다음