개발기록 개발기록

www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 버블소트는 왼쪽에서 오른쪽으로 이동하며 숫자의 위치를 결정한다. 이를 버블소트 그대로 구현하면 문제의 시간조건에 걸린다. 따라서 머지소트로 정렬하며 이동횟수를 세어준다. 왼쪽 배열과 오른쪽 배열을 병합하는 과정에서 오른쪽 배열의 숫자가 선택되어 sorted 배열에 포함된다는 것은 아직 선택되지 않은 왼쪽 배열의 숫자의 갯수만큼 이동한다는 뜻이다. 이를 카운팅한다. #include #include usi..

www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 분할정복으로 풀었다. 다른 사람들의 코드와 비교했을 때, 분할을 위한 매개변수 세팅이 비효율적이었다. 줄 수만으로도 별의 가장 꼭대기 좌표를 설정할 수 있었다. 줄 수는 (별 한 개의 높이) * (별의 개수) 이므로 다음 좌표와 현재 좌표 사이에 상하로 몇 개의 별이 들어갔나 세어보면 되기 때문이다. #include #include using namespace std; int n; int width[12]; int height[12]; char map[3500][..

www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 분할정복 #include #include #include using namespace std; #define MAX 2200 int n; char map[MAX][MAX]; void solve(int y, int x, int k) { if (k == 1) { int t = 0; for (int i = y; i < y + 3; i++) { for (int j = x; j < x + 3;..

www.acmicpc.net/problem/1030 시간별 평면을 다 만드는 것은 메모리 초과가 발생한다. 그리고 정답으로 출력할 최대 크기가 50x50이다. 평면을 만들어 갈 때, 출력범위에 포함되는 부분만 만든다. #include #include #include using namespace std; #define white 0 #define black 1 int S, N, K; int R1, R2, C1, C2; int map[100][100]; bool isBlack(int t) { if ((N - K) / 2 > S >> N >> K >> R1 >> R2 >> C1 >> C2; solve(0, 0, 0, 0); for (int i = 0; i < R2 - R1 + 1; i++) { for (int..

www.acmicpc.net/problem/1725 정답이 나오는 범위를 (왼쪽, 가운데, 오른쪽)으로 나누어 생각한다. #include #include using namespace std; #define MAX 100000 int n; long long a[MAX]; long long solve(int left, int right) { if (left == right) return a[left]; int mid = (left + right) / 2; long long res = max(solve(left, mid), solve(mid+1, right)); int low = mid; int high = mid + 1; long long height = min(a[low], a[high]); res = m..

www.acmicpc.net/problem/2104 왼쪽 부분, 오른쪽 부분, 가운데 부분 중에서 최대값을 찾는다. #include #include using namespace std; #define MAX 100001 #define INF 987654321 int n; long long A[MAX]; long long solve(int left, int right) { if (left == right) return A[left] * A[left]; int mid = (left + right) / 2; long long res = max(solve(left, mid), solve(mid + 1, right)); int low = mid; int high = mid+1; long long m = min(A..

www.acmicpc.net/problem/5904 어림수로 k의 최댓값은 30이하이다. 3개의 조각( s(k-1), 'moooo...', s(k-1)) 중 하나를 타고 들어간다. 3번째 조각을 타고 들어갈 때, n의 인덱스를 s(k-1)에 맞게 갱신해주어야 한다. #include #include #include using namespace std; long long n; long long Size[31]; char S(int k) { if(k == 0){ if (n == 0) return 'm'; else return 'o'; } if (n n; n--; retSize(30); cout

www.acmicpc.net/problem/10830 분할 정복을 이용한 거듭제곱과 연산만 다르고 똑같습니다. #include #include #include #include using namespace std; typedef vector vec; long long N, B; vec map(6, vector(6, 0)); void print(vec v) { for (int i = 0; i B; for (int i = 0; i > map[i][j]; } } map = doMod(map); print(solve(B)); return 0; }