0과 1의 쉼터

풀이 N명의 플레이어가 가진 카드에 대해서 서로 다른 플레이어의 카드 간 배수가 존재하는지 판별하는 문제다. 문제에서 두 번 이상 등장하는 카드는 없다고 하니 해당 번호의 카드의 존재여부를 기록해두면 쉽게 풀이할 수 있다. N명의 player에 대해 카드 번호를 입력받고 i번째 플레이어가 가진 카드가 있다고 표시해주자. 그 다음에는 N명의 player가 가진 카드의 배수에 해당하는 카드가 있는지 확인해주면 된다. 만약 카드 숫자가 i 일 때 카드 숫자가 j 인 카드가 있다면, j % i == 0 즉 j는 i의 배수다. 만약 최대 숫자 1,000,000 (SIZE - 1) 에 대해 i 배수를 탐색했는데 만족하는 카드가 없다면, i 카드를 가진 player는 점수를 얻을 수 없다. 점수를 score 배열에 ..

풀이 "백준 1149, RGB거리"에 조건이 추가된 문제이다. 입력받은 비용들을 여러 번 사용해야 하고, 처음에 고른 색에 따라 최소비용을 계산해주어야 한다. 소스코드 #include #define MAX 1000001 #define MIN(a,b) (a < b ? a : b) int main(){ int N, result = MAX; scanf("%d", &N); int cost[N][3], min[3] = {0,}, old[3] = {0,}; for (int i = 0; i < N; i++) scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]); for (int i = 0; i < 3; i++){ old[0] = old[1] = old[2] = MAX;..

풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"에서 부분 수열의 최대 길이를 lower bound방식으로 빠르게 구했지만, 이렇게 만들어진 임의의 수열들의 요소가 최대 길이를 이루는 요소들이 아님을 예시를 통해 알 수 있었다. 한마디 더 붙이자면, 임시로 생성하는 수열의 최댓값보다 작은 경우에는 lower bound으로 찾은 index위치에 덮어쓰기 때문에 최대 길이를 이루는 요소가 아님을 알 수 있다. 만약 입력받은 요소들이 몇 번째 index에서 덮어쓰기가 되는지 알 수 있다면, 이전의 방법으로 구한 부분 수열의 최대 길이와, 입력받은 요소의 개수 N을 조건에 따라 줄여가면, 요소들을 구할 수 있다. 소스코드 #include #define MAX 1000001 int arr[MAX], te..

풀이 "백준 11053, 가장 긴 증가하는 부분 수열"보다 수열의 크기가 커, 기존의 방법대로 하면 시간초과가 발생한다. 수열 전체에서 binary search로 특정한 조건의 부분 수열을 탐색하는 방법은 아닌 것 같아 lower bound만을 이용했다. 다음과 같이 수열의 길이만을 계산하기 위해 다음과 같이 수열을 만들었다. i = 0이거나, 생성 중인 수열의 가장 뒷 값보다 큰 경우에는 길이를 늘려준다. 위의 조건이 아닐 때마다, lower bound로 적절한 위치에 입력받은 값을 삽입한다. 10 20 10 11 20 와 같은 수열을 입력 받았다고 가정하자. 앞에서 순차적으로 값이 커지는 경우만 계산을 한다면 10 20으로 최대 길이가 2다. 때문에, 11처럼 20보다는 작지만, 10보다는 큰 경우 ..

풀이 n명에 대해서 각각 dfs을 해 만들어진 팀의 학생 수 만큼 전체에서 빼면 된다. 중복을 방지하기 위해, 팀을 짜기 시작한 경우(visited[0])와 탐색이 끝난 경우(visited[1])로 확인을 해주었다. 이전에 만난적 없는 번호이면 짝을 찾아가고, 만난적 있는 짝일 때, 그 짝의 탐색이 끝나지 않은 경우라면 순환이 가능한 즉 팀이 만들어 질 수 있다. 순환점을 발견하기 전 까지 재 탐색을 하며 개수를 세주고, 마지막에 자기 자신을 세어 주면 된다. 소스코드 #include #include #include #define MAX 100001 bool visited[2][MAX]; int arr[MAX], N, cnt; void dfs(int num, int depth){ if (!depth){ ..

풀이 최악의 경우 모든 체스판의 정보가 1로만 이루어질 때, 시간초과가 발생하기 때문에, 효율적으로 풀이해야 한다. 모든 경우를 고려할 때 시간초과가 발생하는 이유 중 하나는 비숍이 규칙적으로 놓일 수 있는 공간에 대해 생각하지 않기 때문이다. 다음처럼 비숍을 놓는 경우를 생각해보자 즉, 흰색과 회색에 놓일 수 있는 비숍으로 구분해서 탐색한다면 규칙적으로 놓일 수 있는 공간대로 탐색할 수 있다. 입력받은 체스판의 정보에 대해 만약 놓을 수 없는 공간이라면 다음 공간으로 넘어가면 된다. 소스코드 #include #include bool board[11][11], l[19], r[19]; int N, result[2]; void bishop(int row, int col, int cnt, int color)..

풀이 "백준 1463, 1로 만들기"와 동일한 문제다. 1로 만드는 과정을 따로 저장해 출력하면 된다. 소스코드 #include #define MAX 1000001 int dp[MAX], arr[MAX] = {0, -1}; int main() { int N; scanf("%d", &N); for (int i = 2; i dp[i/2] + 1) dp[i] = dp[arr[i] = i/2] + 1; if (!(i%3) && dp[i] > dp[i/3] + 1) dp[i] = dp[arr[i] = i/3] + 1; } printf("%d\n", dp[N]); while (N != -1) { printf("%d ", N); N = arr[N]; } } 출처 및 참고자료 12852번: 1로 만들기 2 첫째 줄에 ..

풀이 주어진 예제는 직관적으로 풀이가 가능하지만 주어질 Test Case들을 고려하면 순차적으로 탐색하면서 풀이해야 한다. 우선 첫 번째 행에서 시도해볼 수 있는 모든 경우의 수를 시도한다면, 2~N번째 행에서는 이전 행의 불을 끄면 된다. N번째 행을 검사해서 불이 전부 다 꺼졌다면 입력된 예제가 모두 불이 꺼진 경우이므로 그때 누른 스위치의 개수들의 최솟값을 저장해 출력해주면 된다. 소스코드 #include #include #include #define min(a, b) a < b ? a : b char bulb[10][10], temp[10][10]; const char* lRow = "##########"; int dx[5] = {0, -1, 1}, dy[5] = {0, 0, 0, -1, 1}; ..