본문 바로가기

골드 IV11

[백준 1963] 소수 경로 [C] 풀이 네 자리 수를 하나씩 바꾼 수가 소수이면서, 중복을 피하기 위해 기존에 확인한 수가 아닌 경우에만, 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; .. 2021. 8. 26.
[백준 1153] 네 개의 소수 [C] 풀이 "백준 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 2021. 8. 26.
[백준 2474] 세 용액 [C] 풀이 "백준 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++) .. 2021. 8. 26.
[백준 2239] 스도쿠 [C] 풀이 스도쿠를 완성시키고, 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++).. 2021. 8. 25.
[백준 1806] 부분합 [C] 풀이 연속된 수들의 부분합이기 때문에 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.. 2021. 8. 25.
[백준 9935] 문자열 폭발 [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.. 2021. 8. 24.

티스토리툴바