소스코드33 [C/C++] 17070: 파이프 옮기기 1 이 문제도 (1,2)를 시작해서 graph를 탐색하며 (n,n)까지 가는 경우의 수를 구하는 문제이기 때문에 그래프 탐색 이론을 사용해야한다. 내가 구현한 방식으로는 현재 지점이 이전 지점에서 어떻게 왔냐 (1.가로 2.대각선 3.세로)에 따라서 탐색의 방향을 정했기 때문에 2차원 배열을 이용하여 queue를 사용한 BFS보다는 DFS가 훨씬 쉽다고 판단하여 DFS를 이용하여 문제를 풀었다. DFS에서 이전 지점에서 어떻게 왔냐에 따라 아래 코드처럼 나누었다. void DFS(int n,int x,int y) { if(previous[y][x]==1) //오른쪽으로 감 GoRight(n,x,y); if(previous[y][x]==2) //대각선으로 감 GoDiagonal(n,x,y); if(previo.. 2023. 8. 29. [C] 1026: 보물 결국 함수 S를 최소화하기 위해 배열 A를 재배열 해야한다. 최소화 하기 위해서는 현재 남아있는 A배열에 가장 작은 수와 B배열에 남아있는 가장 큰 수를 곱해줘야지만 S의 값이 최소가 된다. 이 문제에서는 B에 있는 수를 재배열하면 안된다고 했지만 어차피 문제는 답만 맞으면 된다는 생각으로 A는 오름차순으로 B는 내림차순으로 정렬한뒤 같은 index끼리 곱해주었다. 사실 이 문제와 완전 같은 방식으로 하기 위해서는 이차원 배열 두 개를 만든 뒤 현재 남아있는 A배열에 가장 작은 수와 B배열에 남아있는 가장 큰 수를 곱해주고 그 수는 지나갔다는 표시를 남겨주어 다음번에 이 수는 아예 빼고 생각하도록 코드를 짜면 된다. #include int arrA[51]; int arrB[51]; void swap(in.. 2023. 8. 25. [C/C++] 1541: 잃어버린 괄호 이 문제는 -가 언제 나오냐가 중요하다. -가 나올 때 그 다음 -가 나올때 까지 합을 빼는 것이 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 것이다. 또한 -가 나올 때마다 다음 -가 나올 때까지 합을 빼는 것이 가장 최소이기 때문에 현재에 이익이 문제 전체의 이익이 되는 Greedy 알고리즘의 일종이다. 나는 배열 2개만 써서 구현하였지만 아예 -가 나올 때마다 부분 집합을 만들어서 (slice를 통해) 각 값을 더하거나 빼서 구현할 수도 있을 것 같다!! 아래는 소스코드다!! #include #include char arr[52]; int store[3]; int ContinueCalculate(int i,int max) { if(arr[i]=='+') { store[0]+=store[1]; s.. 2023. 8. 24. [C/C++] 6064: 카잉 달력 일단 이 이중 반복문을 통하여 모든 m*n케이스를 찾아보려고 할 경우 제 시간안에 찾아볼 수 없다. 그렇기 때문에 특정 조건일 때만 돌아가도록 만들어줘야 한다. 이 문제는 결국 x+M*a=y+N*b 라는 a와 b에 관한 부정방정식을 푸는 것인데 결국 이는 답이 되는 수를 t라고 한다면 t%M==x t%N==y가 되도록 만들어줘야한다. 그렇기 때문에 while문에 들어가는 초기 변수가 j=x_target이 된 것이고 while문을 한번 돌때마다 x만큼 증가시켜주면서 만족하는 수가 있는지 확인해줘야한다. 한가지 유의해야할 점은 x==x_target && y==y_target일 때인데 사실 이 경우 x%x_target이 x가 아니라 0이므로 이때를 주의하여 코드를 작성해야한다. 또한 이 경우에는 gcd 유클리.. 2023. 8. 24. 이전 1 ··· 3 4 5 6 7 8 9 다음
