Dolphins의 HelloWorld

문제링크 : 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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl47b6DGMDFAXm&categoryId=AWVl47b6DGMDFAXm&categoryType=CODE&&& 주어진 문제를 풀기위해 string 형식으로 위의 괄호 표현을 받은 후 반복문을 통해 첫번째 괄호부터 검사를 해나갔다. 먼저 '(' 를 탐색했을 떄는 다음 배열을 탐색하여 이것이 레이저인지, 쇠막대기가 추가되는 것인지 검사를 하였다. 쇠막대기가 추가된 것이라면 변수에 쇠막대기의 갯수를 추가해주고 레이저라면 현재 있는 쇠막대기의 수 만큼 결과값에 더해주도록 하였다. 위의 그림을 예로들자면 두번째 레이저가 나왔을 떄는 쇠막대기가 3개있는 상태기..

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

문제 링크 : https://www.acmicpc.net/problem/1080 #include #include using namespace std; int A[50][50]; int B[50][50]; int main() { int N, M; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%1d", &A[i][j]); } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%1d", &B[i][j]); } } int count = 0; for (int i = 0; i < N-2; i++) { for (int j = 0..

문제 링크 : https://www.acmicpc.net/problem/1201 비슷한 문제를 풀 때 활용할만한 부분이 있어서 개념부분으로 따로 뺀 문제이다. 먼저 어떤 경우에 문제의 조건에 맞게 최대 부분 증가 수열의 길이가 M이고 최대 부분 감소 수열의 길이가 K인 수열을 출력할 수 있는지 살펴보겠다. 일단 주어지는 수 N은 M+K-1 이상이어야 한다. 당연히 증가,감소 수열이 한번씩은 나와야 하기 때문에 M+K라는 수식이 나오는 것이며 1이 빠지는 이유는 두 수열이 숫자 하나를 공유하기 때문이다. 예를들어 위의 예시에서 2 1 4 까지 보면 증가, 감소 수열이 하나씩 나타나는데 이 수열이 1을 공유하고있음을 볼 수 있다. 다음으로 N은 M*K보다는 작거나 같아야 한다. 예를들어 만약 M이 3이고 K..

문제링크 : https://www.acmicpc.net/problem/1783 처리하는 방법이 높이에 따라 3가지로 나뉜다. 1. 높이가 1인경우 -> 제자리 말고 이동할 수 있는 칸이 없으므로 갯수는 1 2. 높이가 2인 경우 -> 2칸씩 위, 아래로가는 1번,4번 방법을 쓸 수 없고 4번이상 이동할 경우 모든 방법을 다 써야하므로 제일 많이 가봐야 제자리 1칸 + 이동 3칸 = 4칸이다, 가로 길이가 충분하지 않은 경우 (M+1)/2 하면 칸의 갯수가 되며 min(4,(M+1)/2)를 통해 구해주면 된다. (이해가 안될 경우 직접 그리면서 이해해보자.) 3. 높이가 3인 경우 -> 이 때는 너비가 7이상일 떄와 미만일 때로 경우가 나뉘는데 그 이유는 4가지 방법을 모두 쓰면 기본적으로 가로 7의 거리..

문제 링크 : https://www.acmicpc.net/problem/10610 30 = 3 * 10 이며 10의 배수는 0이 필요하고 3의 배수는 각 자리 숫자의 합이 3의 배수라는 성질이 있으므로 이 성질들을 이용하여 코드를 짜 보았다. #include #include #include using namespace std; int arr[10]; int main() { string N; cin >> N; int sum = 0; memset(arr, 0, sizeof(int) * 10); for (int i = 0; i < N.size(); i++) { int num = N[i] - '0'; sum += num; arr[num]++; } string result = ""; if ((sum % 3 != ..

문제링크 : https://www.acmicpc.net/problem/2875 K가 0이 될 때까지 반복하면서 만약 여자의 수가 남자의 2배보다 크면 여자의 수를 하나씩 낮추었고 그렇지 않다면 남자의 수를 낮추면서 수를 조정하였다. #include using namespace std; int main() { int N, M, K; cin >> N >> M >> K; while (K--) { if (N > 2 * M) N--; else M--; } int result; if (N >= 2 * M) result = M; else result = N / 2; printf("%d\n", result); }