Dolphins의 HelloWorld

문제링크 : https://www.acmicpc.net/problem/1697 풀이 문제 분류가 DFS, BFS로 되어있고 실제로 정답을 맞춘 사람들의 풀이를 보면 큐를 이용해서 푼 사람들이 대부분이지만 난 그냥 Dynamic Programming 으로 풀었다. Dynamic Programming으로 푼다고하면 아마 초기값 설정에서 애매하게 느낄 수 있겠지만 난 그냥 수빈이 위치 이전값들은 걸어서 이동하는 것 밖에 방법이 없으므로 수빈이 위치를 0으로 놓은 상태에서 1씩 증가시키면서 일일히 다 넣어주었다. 그런다음 수빈이 위치 + 1 부터 동생의 위치 + 1까지 for문을 통해 반복문을 진행하면서 만약 인덱스 i가 짝수라면 다음과 같이 arr[i] = min(arr[i / 2] + 1, arr[i - 1..

문제링크 : https://www.acmicpc.net/problem/6603 풀이 주어진 k개의 번호중 6개를 골라 만들 수 있는 경우를 모두 구하는 문제이다. 6개를 고르기 위해 순열의 특성을 이용했는데 예를들어 숫자가 7개가 있다고 가정하고 0을 1개 1을 6개를 배열에 넣고 모든순열을 구하면 다음과같이 나온다. 이 부분에서 아마 이 문제를 어떻게 풀어야할지 대충 감이 왔으리라 생각된다. 이렇게 k-6개에 대해 0을 넣고 k개의 1을 넣은 후 순열을 돌렸을 때 1이 있는 곳과 대응되는 자리의 수를 출력하면 모든 경우를 구할 수 있는것이다. 소스코드는 다음과 같다. #include #include #include using namespace std; int main() { while (1) { int..

문제링크 : https://www.acmicpc.net/problem/10971 풀이 외판원이 순회할 수 있는 경로를 모두 검사하면서 그 중 가장 최솟값을 구하면 문제를 풀 수 있다. 순회 경로같은 경우 만약 N=4라면 배열에 0 1 2 3 을 넣어놓은 후 next_permutation함수를 통해 구해주었고 순열이 바뀔 때마다 경로비용의 합을 구해주면서 최솟값을 추출하도록 하였다. #include #include using namespace std; int arr[10][10]; int permutation[10]; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d..

문제링크 : https://www.acmicpc.net/problem/10819 풀이 순열을 모두 검사하여 문제에서 제시한 연산을 했을 때 가장 큰 수를 출력하면 되는 문제이다. #include #include using namespace std; int N; int calculate(int* arr) { int result = 0; for (int i = 0; i < N-1; i++) { result += abs(arr[i] - arr[i + 1]); } return result; } int main() { int arr[8]; scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &arr[i]); sort(arr, arr + N); int answer ..

문제 링크 : https://www.acmicpc.net/problem/1107 #include #include using namespace std; bool not_work[10]; int channel(int num) //버튼이 고장나지 않았다면 해당 채널의 자릿수 반환 { int len = 0; do { len++; if (not_work[num % 10]) //버튼이 고장나있다면 0 반환 return 0; num /= 10; } while (num != 0); return len; } int main() { int N, num; //틀고자하는 채널, 고장난 버튼의 수 int tmp; //그냥 임시적으로 쓰는 변수 scanf("%d %d", &N, &num); for (int i = 0; i < n..

문제링크 : https://www.acmicpc.net/problem/1939 풀이 문제를 어떻게 풀까 하다가 이진탐색과 DFS를 결합하기로 하였다. DFS같은 경우 경로를 따라 다리를 건널 때 DFS함수에 매개변수로 넣어준 하중이 다리가 견딜 수 있는 하중보다 높으면 다리를 못건너도록 하여 트럭이 목적지까지 가면 따로 지정해준 전역변수에 true를 할당하도록 하였고 목적지까지 가지 못한다면 false를 할당하도록 하였다. 나머지 과정은 그 true인지 false인지에 따라 처리를 달리해주며 무게에 따라 이진탐색을 계속 하도록 하였다. #include #include #include using namespace std; vector v[100001]; bool map[100001]; int start_p..

문제링크 : https://www.acmicpc.net/problem/2110 문제를 풀기 위해서 먼저 sort함수를 이용하여 입력받은 집의 좌표를 오름차순으로 정렬한다. 다음으로 left = 1 , right = 맨 뒤의 좌표 - 맨 앞의 좌표 로 하여 이진탐색을 수행한다. 특정 거리에 이르기 까지는 원하는 수의 공유기를 충분히 놓을 수 있지만 그 특정 거리에서 하나라도 커지는 순간 원하는 숫자의 공유기를 놓지 못한다는 점을 이용한다. #include #include using namespace std; int N, C; long long house[200000]; bool gap(long long num) { int start = 0; int cnt = 1; for (int i = 1; i < N; ..

문제링크 : https://www.acmicpc.net/problem/2805 풀이 절단기에 설정할 수 있는 높이의 최댓값을 구하기 위해 높이를 하나하나 넣어주면서 비교를 해 주어야 하는데 전수조사를 하면 복잡도가 너무 높기 때문에 이진탐색을 사용해 준다. 범위중에 가장 작은 수인 1을 left, 주어진 나무의 높이중 가장 높은것을 right로 하여 이진탐색을 진행하게 된다. #include using namespace std; long long tree[1000000]; int N; long long M; bool cut(long long num) { long long result = 0; for (int i = 0; i num) { result += (t..

문제링크 : https://www.acmicpc.net/problem/1654 문제를 읽고나면 전수조사를 통해 해결할 수 있기는 하지만 분명 그런방식으로는 시간초과가 일어나 문제를 해결할 수 없을 것이라는 걸 예측할 수 있다. 그렇게 때문에 사용해준 방식이 이진탐색을 이용한 방식이다. 먼저 최솟값을 1, 최댓값을 랜선 중 가장 큰 수로 놓고 시작하기로 하였다. 또한 예를들어 문제의 예제를 통해 보면 답인 200보다 작을 때는 자른것의 합이 11보다 크거나 같지만 201이 되는순간 10이 되는것을 알 수 있기 때문에 이런 특성을 이용해서 이진탐색이 끝날 떄까지 자른것의 합이 n보다 크거나 같은것중 가장 큰 값을 계속 변수에 할당하도록 하였다.

문제링크 : https://www.acmicpc.net/problem/1780 분할 정복을 통해 풀 수 있는 문제이다. 따로 2개의 함수를 정의했는데 하나는 모든 수가 같은지 체크하는것, 또 다른 하나는 분할정복을 가능하게 하는 함수이다. 모든 수가 같은지 체크하는 것은 그냥 주어진 종이를 둘러보며 하나라도 숫자가 다르면 false를 return하고 모두 같다면 true를 return 하도록 하였다. 중요한것은 분할 정복을 가능하게 만드는 함수이다. 인자로 가장 맨 왼쪽 위의 점과 종이의 길이를 주었다. 먼저 그 함수에 들어가면 종이 안의 모든 숫자가 같은지 check를 한 다음에 만약 같다면 어떤 숫자인지 확인해서 결과값을 조정하였고 만약 숫자가 같지 않다면 그 종이를 9등분으로 짤라서 같은 과정을 다..