본문 바로가기

class 521

[백준 2467] 용액 [C] 풀이 특성값의 합이 기존에 구한 특성값의 합보다 작다고 항상 0에 가까운건 아니다. ex) -1 + 1 = 0, -10 + 1 = -9 때문에 특성값 합의 절대값을 이용해 구해야한다. 새로운 특성값 합의 절대값이 기존 특성값 합의 절대값보다 작을 때, 새로운 특성값의 합과, 두 용액의 특성값 또한 새로 담아주어야 한다. 소스코드 #include #include int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); int left = 0, right = N-1, sum = 2e9; int left_val = arr[left], right_val = arr[right]; while (le.. 2021. 8. 26.
[백준 1005] ACM Craft [C] 풀이 건물 W를 완성하기 위해서는 건물 1에서 건물 W로 향하는 건물들이 완성되어야 하기 때문에, W값에서 역으로 DFS방식을 사용했다. W에서 1로 향하는 건물들이 모두 건설되어야 하기 때문에 D값이 가장 큰 값을 time에 넣어주어 반환해야 한다. 좀더 효율적인 탐색을 위해 총 time을 check에 넣는 memoization방식으로 해결했다. 단, D값은 0이상이기 때문에 -1로 초기화해서 사용해야 한다. 소스코드 #include #include #include #define max(a, b) a > b ? a : b int D[1001], N, check[1001]; bool O[1001][1001]; int construction(int c){ if (check[c] != -1) return c.. 2021. 8. 25.
[백준 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.
[백준 2166] 다각형의 면적 [C] 풀이 "백준 11758, CCW"를 이용해 풀이했다. 벡터곱의 값은 두 벡터로 이루어지는 평행사변형의 넓이와 동일하므로, 벡터곱의 값을 반으로 나눈 값을 더해주면 된다. 기준점이 필요하기 때문에 처음에 입력받은 좌표를 기준점으로 했다. 소스코드 #include typedef struct{ double x, y; }Point; int main(){ int N; scanf("%d", &N); Point p[N]; for (int i = 0; i < N; i++) scanf("%lf %lf", &p[i].x, &p[i].y); double sum = 0; for (int i = 1; i < N; i++) sum += ((p[i-1].x - p[0].x)*(p[i].y - p[0].y) - (p[i-1].y -.. 2021. 8. 25.
[백준 9527] 1의 개수 세기 [C] 풀이 16까지 1의 분포는 다음과 같다. N N의 2진수 1의 개수 1 1 1 2 1 0 2 3 1 1 4 4 1 0 0 5 5 1 0 1 7 6 1 1 0 9 7 1 1 1 12 8 1 0 0 0 13 9 1 0 0 1 15 10 1 0 1 0 17 11 1 0 1 1 20 12 1 1 0 0 22 13 1 1 0 1 25 14 1 1 1 0 28 15 1 1 1 1 32 16 1 0 0 0 0 33 2^x 자리 수는 2^(x+1)마다 반복된다는 것을 알 수 있다. 때문에, (N+1)을 2^(x+1)로 나눈 몫을 2^x만큼 곱하면 완전히 반복되는 구간에 존재하는 1의 개수를 구할 수 있다. 완전히 반복되지 않은 구간에서의 1의 개수는, 2^x 자리 수가 1인경우 (N+1)을 2^x로 나눈 나머지의 개수.. 2021. 8. 25.

티스토리툴바