https://www.acmicpc.net/problem/6064 카잉달력은 에서 까지 존재하며, 해에는 멸망의 해가 된다.또한 의 다음해는 x 따라서 M = 10, N = 12인 경우 , , , , , , , , , , , ...이 된다. 카잉 달력의 51번째 해를 구할려면 어떻게 해야할까?51번째 해는 M인 10이 5번 들어가고 그 후 1해가 지나가면 51번째 해가된다. ( x = 1 )마찬가지로 N인 12가 4번 들어가고 그 후 3해가 지나가면 51번째 해가된다. ( y = 3 ) 멸망해는 M과 N이 동시에 들어가는 최소공배수가 된다.위 조건대로 멸망해의 최소공배수를 구하면 60이 된다. 먼저 예제의 경우를 보자10 1239i = 3i = 13i = 23i = 33 .....이런식으로 for문을 ..
Baekjoon Review
https://www.acmicpc.net/problem/18111 N x M 크기의 땅 정보를 입력 받을 때 최소 높이의 블록과 최대 높이 블록을 구한다.이후 최소 높이에서 최대 높이까지 땅 높이를 조사한다.현재 높이에서 arr배열 속 땅 정보가 크면 땅을 판다.또한 현재 높이에서 arr배열 속 땅 정보가 작으면 땅을 채운다. #include #include using namespace std;int N, M, B;int arr[501][501];int minBlock = 257, maxBlock = 0;int answer = 987654321, height = -1;void dfs(int h, int b){ int t = 0; for(int i = 0;i h){ ..
https://www.acmicpc.net/problem/17626 #include using namespace std;int dp[50005];int N;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>N; for(int i = 1;i
https://www.acmicpc.net/problem/2805 배열에 잘라야할 나무를 담는다. 이후 배열을 정렬한다.정렬하는 이유는 자를 수 있는 최대 높이를 구해야하기 때문이다. 자를 최소 높이를 0으로 하고 최대 높이를 배열의 마지막 요소로 정했다면최소와 최대가 서로 교차되지 않을 때까지 반복을 진행한다. 자를 길이는 low와 high 합 / 2로 결정한다. 이유는 binary_search를 하기 위함이다.배열 요소에 자를 길이를 뺀 결과가 0보다 큰 경우 sum에 뺀 결과를 누적한다.sum이 가져갈 나무의 길이보다 큰 경우 현재 자를 길이를 저장하고, 최소 높이를 자를 길이의 + 1로 결정한다.만약 작은 경우 최대 높이를 자를 길이의 - 1로 결정한다. #include #include #incl..
https://www.acmicpc.net/problem/18870 이 문제에서는 생소한 stl 함수를 사용하였다. lower_bound 함수는 인자로 넘겨준 배열의 포인터들 사이에서 target값이 처음 나오는 인덱스의 iterator를 반환한다.iterator를 반환하기 때문에 인덱스를 알고 싶다면 배열의 경우 배열의 첫번째 위치를 빼고 벡터의 경우 v.begin()을 빼면 된다. 코드에서 정렬과 같은 값을 빼준 이유는 lower_bound함수를 사용하기 위해서다.문제의 좌표값은 수직선 상에 존재하기 때문에 같은 값은 같은 위치를 나타낸다. 또한 인덱스를 통해 압축할 좌표의 위치를 알기 위해서는 정렬을 통해 수직선 상에 나타내야 한다. #include #include #include #include..
https://www.acmicpc.net/problem/2630 문제에서 NxN크기의 종이를 NxN, N/2xN/2, ... 크기 순서로 자르라고 나타나있다.따라서 0, 0 자리부터 탐색을 시작하고, NxN크기부터 자를 수 있는지 판단한다. 판단의 기준은 0번째 자리부터 N번째 자리까지 탐색을 진행한 후처음 색과 진행과정 중 발견한 색이 다를 경우 자른다. #include #include #include #include using namespace std;int N;int arr[129][129];int white = 0;int blue = 0;void dfs(int y, int x, int cnt){ bool cut = false; int color = arr[y][x]; for(in..
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트리이를 공부하다 찾은 문제이다. 트라이는 문자열을 효율적으로 탐색할 수 있는 자료구조이다. 문제에서 전화번호 목록이 아래와 같이 주어진 경우 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 선영의 전화번호를 입력할 경우 입력 중 긴급전화로 연결되어 일관성이 없는 목록이 된다. 따라서 전화번호를 입력 받고 각 전화번호가 연관성이 있는지 검사하면 된다..
https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 이 문제는 그리디 알고리즘을 사용해서 해결할 수 있다. 문제에서 각 박스의 정보가 입력으로 들어온다. 박스의 정보는 보내는 마을 번호, 받는 마을 번호, 박스의 개수가 있다. 입력으로 받기 위해 pair 자료형을 사용했다. 또한, 박스 정보를 도착 마을 순서로 정렬하여 탐색 시 가장 작은 도착 마을부터 할 수 있도록 하였다. 그 이유는 보내는 마을과 받는 마을이 가까울수록 많이..
