0과 1의 쉼터

풀이 네 자리 수를 하나씩 바꾼 수가 소수이면서, 중복을 피하기 위해 기존에 확인한 수가 아닌 경우에만, Queue에 담아주고, 자리수를 바꾸기 전의 수의 변환 횟수에 1을 더한 값을 자리수를 바꾼 후 숫자의 변환 횟수에 입력해주었다. 소스코드 #include #include #include #include #define MAX 10000 bool cNum[MAX]; int cnt[MAX], queue[MAX]; void bfs(int old, int pw){ int front = -1, rear = -1, n; cnt[queue[++rear] = old] = 0; while (front < rear){ if ((n = queue[++front]) == pw) return; for (int i = 0; ..

풀이 "백준 6588, 골드바흐의 추측" 코드를 이용해 풀이했다. 단, 골드바흐의 추측은 짝수인 N에 대해 해당하기 때문에, 입력받은 N이 홀수인 경우 2, 3을, 짝수인 경우 2, 2를 먼저 출력해준 후 출력해준 수 만큼 빼준 N값에 대해 골드바흐의 추측을 사용해 풀이할 수 있다. 단, 8인 경우에는 2, 2, 2, 2이기 때문에 따로 써주거나 더 안정적인 골드바흐의 추측 알고리즘을 사용하면 된다. 소스코드 #include #include #include #define MAX 1000001 bool Cnum[MAX]; int main(){ int sq = sqrt(MAX); for (int i = 2; i

풀이 "백준 2470, 두 용액"의 응용 문제이다. 세 개의 특성값을 비교해야 하므로, 맨 왼쪽부터 기준이 되는 idx번째 특성값과, idx+1 ~ N-1의 특성값을 더해 0에 가장 가까운 용액을 만들어내는 특성값을 찾으면 된다. 단, 세 개 특성값의 최댓/최솟값이 int 범위를 벗어나므로, llabs()를 사용하고, 연산의 범위를 long long으로 선언했다. 소스코드 #include #include #define ll long long int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) ..

풀이 스도쿠를 완성시키고, 81자리의 수가 제일 작은 경우를 출력하면 되는 문제이다. Backtracking방식으로 스도쿠에 넣어줄 수 있는 작은 수 부터 탐색하면서, 만약 81번째 자리에 도달했다면 가장 작은 81자리의 수를 완성시킨 것이기 때문에 출력을 해주고 중단을 해줘야한다. 소스코드 #include int arr[9][9], print = 1; int check(int x, int y, int val){ for (int i = 0; i < 9; i++) if (arr[x][i] == val || arr[i][y] == val) return 0; x = (x/3)*3; y = (y/3)*3; for (int i = x; i < x+3; i++) for (int j = y; j < y+3; j++)..

풀이 연속된 수들의 부분합이기 때문에 Two Pointers로 쉽게 구현할 수 있다. start, end가 가르키는 배열의 합들이 S이상이면 최소 길이를 구해야 하며, 만약 sum이 S보다 작으면 end+1번째 요소를 더해주고, 그렇지 않다면 start번째 요소를 빼주는 방식으로 풀이했다. 소스코드 #include #define min(a, b) a < b ? a : b int main(){ int arr[100000], N, S, start = 0, end = 0; scanf("%d %d %d", &N, &S, &arr[0]); for (int i = 1; i < N; i++) scanf("%d", &arr[i]); int cnt = 1e5, sum = arr[0]; while (start = S) c..

풀이 문자열의 길이가 폭발 문자열의 길이보다 크거나 같을 때, 폭발 문자열을 포함하고 있으면, 폭발 문자열의 길이만큼 index를 감소시키는 방식으로 출력할 문자열을 만들어주었다. 최종적인 index만큼 출력을 해줘도 되고, 마지막에 '\0'을 삽입해 문자열의 끝을 알려줘도 된다. 소스코드 #include #include char str[1000001], ans[1000001], explosion[37]; int main(){ scanf("%s %s", str, explosion); int len = strlen(str), exp_len = strlen(explosion), idx = 0; for (int i = 0; i = e..

풀이 분할 정복을 이용한 거듭제곱 알고리즘으로 행렬의 제곱을 구현해주어야 시간 초과가 발생하지 않는다. 소스코드 #include int N; void square(int result[][5], int matrix[][5]){ int temp[5][5] = {0,}; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) temp[i][j] += (result[i][k]*matrix[k][j]) %1000; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) result[i][j] = temp[i][j] %1000; } int main(){ long long B; ..

풀이 가장 큰 방 번호는 만들어 질 수 있는 가장 긴 방 번호와 작거나 같다.. 따라서, 가격이 가장 저렴한 방 번호로 가장 긴 번호를 만들고, 번호의 앞자리 부터 남은 M을 이용해 가능한 큰 수로 바꾸어 주면된다. 단, 앞자리에 0이 올 수 있는 경우는 방 번호가 0인 경우만 가능하므로 M이 작아 9~1의 번호로 교체가 불가능해 여전히 0이라면, 교체가 가능할 때까지 min만큼 다시 M에 더해주어야 한다. 소스코드 #include int main(){ int N, M; scanf("%d", &N); int price[N], min = 50, idx; for (int i = 0; i = price[i]){ min = price..

풀이 1과, 2의 답은 방 마다 bfs를 사용해 탐색하면 쉽게 구할 수 있다. 3의 답은 방의 각 칸에서 모든 방향으로 벽을 부셔보고 bfs를 사용해 탐색하면 되는데, 매번 방문한 장소를 초기화해주고, 벽을 뚫었다가 탐색이 끝나면 다시 막아주어야 한다. 방향의 순서는 문제에 주어진대로 bit값의 shift연산과 관련이 있으므로 서, 북, 동, 남 순서대로 탐색했다. 소스코드 #include #include #include #define MAX 50 int n, m, graph[MAX][MAX], rear; bool visited[MAX][MAX]; typedef struct{ int x, y; }Point; Point queue[MAX*MAX], d[4] = {{0,-1}, {-1,0}, {0,1}, {..

풀이 별로 만들어지는 삼각형의 높이와 너비는 각각 2^(N) -1, 2^(N+1) -3이다. 다음은 N=3일 때의 예제이다. 빨간 사각형은 mark_star(x, y, n)을 Recursive Call할 때 해당하는 영영이고, (x, y)는 맨 좌측상단이며, N=1때 는 (x, y)와 영역이 일치하므로 별을 찍어주고 함수를 종료한다. 연두색과 하늘색 공간의 별은 다음과 같이 찍었다. for (int i = 0; i < width; i++) arr[x+(n%2 ? height-1 : 0)][y+i] = '*'; // 연두색 for (int i = 0; i < height; i++){ if (n%2) arr[x+i][y+width/2-i] = arr[x+i][y+width/2+i] = '*'; // 하늘색 ..