0과 1의 쉼터

풀이 주어진 예제는 직관적으로 풀이가 가능하지만 주어질 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}; ..

풀이 에라토스테네스의 체로 소수가 아닌 수들을 찾고, 입력받은 N부터 소수인 수들중에 팰림드롬인지 확인해서 맞으면 해당 수를 출력하고 탐색을 종료하면 된다. 단, 98689 이후의 수들이 갖는 최소의 펠림드롬 소수는 1003001이므로 예외처리를 해주어야 한다. 소스코드 #include #include #include #include #define MAX 1000001 bool cNum[MAX] = {0, 1}; int main(){ int sq = sqrt(MAX); for (int i = 2; i 98689) puts("1003001"); else for (int i = N; i < MAX; i++) if (!cNum[i]){ char str[7]; sprintf(str, "%d", i); int l..

풀이 단순히 가장 큰 제곱수로 수를 구성하는 방법은 최소 제곱수의 개수의 만족이 성립하지 않는다. 때문에, 입력받은 n까지 모든 수에 대해 계산을 해봐야 한다. Square Free Integer같은 경우 이전의 수를 구성하는 제곱수의 개수 + 1을 만족하며 이러한 수의 밀집도는 리만 가설이 참이라는 전제하에 약 61%이다. ("백준 1557, 제곱 ㄴㄴ" 중 "Mobius function의 반환값의 개수 추측") 따라서 다음과 규칙을 기본으로 사용했다. for (int i = 1; i = 4 일 때는 Square Free Integer가 아닌 수들도 존재하며, 처음에 언급했듯이 가장 큰 제곱수의 구성이 최소 제곱수의 개수를 만족하지 않으므로, 구성 가능한 제곱수들 중 최소 제곱수의 개수를 찾아야 한다...

풀이 256 ~ 0까지 모든 높이의 평지를 만들어보며 최단 시간을 구하는 문제이다. 동일한 층의 개수를 배열로 입력받았고, 가장 높은 층을 구했다. 최단시간이 동일하다면, 높이가 가장 높은 것을 출력해야 하기 때문에 256부터 0으로 내려가면서 탐색했다. (만약 시간이 동일하다면 높은 층의 기록이 유지되므로) 최대 시간(result)은 다음과 같다. 땅의 크기(500 x 500) x 설치(2) x 최대높이(256) = 128,000,000 소스코드 #include int main(){ int N, M, B, arr[257] = {0, }, temp, max = 0; scanf("%d %d %d", &N, &M, &B); for (int i = 0; i < N*M; i++){ scanf("%d", &tem..

풀이 난이도에 비해 조금 까다로운 문제이다. n을 포함하는 범위(min ~ max)를 알아낸 후, n을 포함하는 범위의 개수를 알아내야 한다. 소스코드 #include #include int compare (const void *a, const void *b){ int n1 = *(int*)a, n2 = *(int*)b; if (n1 n2) return 1; return 0; } int main(){ int L, n; scanf("%d", &L); int S[L]; for(int i = 0; i < L; i++) scanf("%d", &S[i]); scanf("%d", &n); qsort(S, L, sizeof(int), compare); int m..

풀이 키와 몸무게 둘다 큰 경우에만 cnt를 증가시켜준다. 소스코드 #include typedef struct{ int x, y; }Size; int main(){ int N; scanf("%d", &N); Size s[N]; for (int i = 0; i < N; i++) scanf("%d %d", &s[i].x, &s[i].y); for (int i = 0; i < N; i++){ int cnt = 0; for (int j = 0; j < N; j++) if (s[i].x < s[j].x && s[i].y < s[j].y) cnt++; printf("%d ", cnt + 1); } } 출처 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다...

풀이 666이 포함된 수가 나오는 순서와 입력된 값이 일치할 때 까지 수를 증가시키면 된다. 소스코드 #include int main(){ int N, cnt = 0, result, temp; scanf("%d", &N); for (result = 665; cnt < N;){ temp = ++result; while (temp) if (temp % 1000 == 666){ cnt++; break; }else temp /= 10; } printf("%d\n", result); } 출처 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 ww..

풀이 5kg 봉지를 최대한 많이 들때, 배달하는 봉지의 개수가 최소인점을 이용해 풀이했다. 입력받은 N을 5(kg)로 나누었을 때 나머지가 0이면 몫이 봉지의 개수이다. 나머지가 0이 아니라면, 몫(cnt)을 한 개씩 줄이고, 3(kg)봉지를 몇개를 추가해야 알맞게 배달할 수 있는지 계산한다. 만약, 나누어 떨어지지 않는다면 cnt는 -1로 감소하며, -1을 출력할 것이다. 소스코드 #include int main() { int N, cnt = 0; scanf("%d", &N); cnt = N / 5; if (N % 5) for (; cnt >= 0; cnt--) if ((N - 5 * cnt) % 3 == 0) { cnt += (N - 5*cnt) / 3; break; } printf("%d\n", c..

풀이 4673 - 셀프 넘버 문제와 비슷하다. 단, 생성자의 여부가 아닌, 가장 작은 생성자를 출력해야 한다. 생정자의 범위는 N - 자리수 * 9 부터 N-1이다. 만약 생성자를 구하지 못했다면, 0을 반환한다. 소스코드 #include int selfNum(int n){ int cnt = 0, temp = n; for (; temp > 0; temp /= 10) ++cnt; for (int i = n - 9*cnt; i 0; temp /= 10) result += temp%10; if (result == n) return i; } return 0; } int main(){ int N; scanf("%d", &N..

풀이 하나의 행에는 하나의 퀸만 존재한다는 점을 이용해, 배열의 index는 행, value는 퀸의 위치로 구현했다. nQueen() 0행 부터 Brute Force 방식으로 퀸이 놓일 수 있는지 확인하고, cnt값을 조작한다. put_check() 현재 행(index)의 value(퀸의 위치)가 다음 행의 value와 일치한다면, 동일한 열에 퀸이 놓인 것 이므로, 다음 열에 퀸을 놓는 경우로 넘어간다. 현재 행(row)에서 이전 행(i)들을 뺀 값이 현재 행의 value(퀸의 위치)에서 이전 행의 value를 뺀 절대값과 동일하다면, 동일한 대각선 상에 퀸이 놓인 것 이므로, 다음 열에 퀸을 놓는 경우로 넘어간다. 소스코드 #include #include int N, board[15], cnt; in..