4 Problem B : 타일 채우기
정사각형 모양의 바닥을 타일로 채우려고 함 타일의 모양 4가지가 존재함 홀의 위치를 입력 받고, 홀을 제외한 나머지 부분은 빈 공간 없이 타일을 채우는 프로그램을 작성하시오 - 분할 정복 - 홀의 위치 - 재귀로 풀이 가능 - 행,렬 명확히 구분 #include #define MAX 520 int tile[MAX][MAX]; int dy[4] = { 0, 0, 1, 1 }, dx[4] = { 0,1,0,1 }; void fill(int n, int sy, int sx, int hy, int hx) { if (n < 2) return; // n==1이면 return int m = n / 2, my = sy + m, mx = sx + m, y, x; // 중간위치가 어디인지 확인 int hp = hy/my ..
2019. 11. 7.
4 Problem A : 책 복사하기
책의 권수 m과 서기공의 수 k가 주어진다 가장 많은 페이지를 맡은 서기공의 페이지 수를 최소화할 수 있도록, 책들을 k명의 서기공에게 배분하는 프로그램을 작성하라 가능한 범위를 선정하고, 그에 따라 배분한 후 출력 #include #define MAX 510 // 책이 들어오는 수 typedef long long LL; // 책, 책 누적값 int m, k, maxp; LL book[MAX], sum[MAX]; void input() { scanf("%d %d", &m, &k); maxp = 0; for (int i = 1; i k) return 0; // cnt 가 } } return 1; } int b_search() { int s = maxp, e = sum[m], m; // 최소와 최대 범위를 ..
2019. 11. 7.
2 Problem F : 합이 0이 되는 4개의 숫자들
숫자를 원소로 가지고 있는 A, B, C, D 집합이 있음 a + b + c + d = 0 인 경우의 수가 몇 가지인가 계산하는 프로그램을 작성하라 집합의 크기가 4,000 가능하므로 완전 탐색의 경우 (4,000)^4 시간 초과 발생 따라서 4,000^2 으로 두 부분 집합으로 만들고, radix sort 후 sliding window 로 시간을 줄일 수 있다 #include //#define tet_MAX 30010 #define tet_MAX 31 int N, M, H, P, tet[tet_MAX], gogo[3]; // 테트의 위치를 비트로 표현함 void rotate(int b[3][3]) { int a[3][3], i, j; for (i = 0; i < 3; i++) for (j = 0; j ..
2019. 11. 6.
3 Problem A : 비밀편지
2진수로 이루어진 6자리 비트 패턴이 8개 존재한다 여기서 새로들어오는 입력과 비교하여 비트 한개가 다른 것 까지 허용한다 비트 연산 &, ^를 사용하여 패턴과 들어온 2진수를 비교한다 이때 뒤에서부터 계산하는 것을 확인한다 #include int pattern[8] = { 0, 15, 19, 28, 38, 41, 53, 58 }; int chk(int num) // ^ & 비트연산 사용하여, 하나만 다른지 확인하기 { int i, dif; for (i = 0; i < 8; i++) { dif = (num ^ pattern[i]); // 비교해서 다른 것 저장 if ((dif & (dif - 1)) == 0) break; // 하나가 다르거나, 같으면, } return i; } int main() { i..
2019. 11. 6.
