plzfday's notes

[BOJ] 1026번: 보물 풀이 한 쪽 배열은 오름차순, 다른 한 쪽은 내림차순하면 된다. 코드 #include #include #include using namespace std; int main() { int n; char A[51], B[51]; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &A[i]); for (int i = 0; i < n; ++i) scanf("%d", &B[i]); sort(A, A + n); sort(B, B + n, greater()); unsigned int sum = 0; for (int i = 0; i < n; ++i) { sum += (A[i] * B[i]); } printf("%d\n", sum); ret..

11819번: The Shortest does not Mean the Simplest 풀이 모듈러 연산의 특징 을 알고 있어야 풀 수 있는 문제다(+센스). 여기서는 모듈러의 곱셈, 덧셈 특징이 적용되기에 내용만 적자면 이렇다. 참고: 모듈러 연산 성질 곱셈: (A*B) mod C = ((A mod C) * (B mod C)) mod C 덧셈: (A+B) mod C = ((A mod C) + (B mod C)) mod C 제곱을 할 때 이것을 써야 하고, 사실 이 문제는 long long 범위를 곱할 때도 그냥 넘겨 버리기 때문에 우리가 쓰는 곱셈을 그냥 쓰면 안 되고 덧셈으로 바꿔서 계산해야 한다. 하지만 일반적인 생각으로 곱셈 구현을 하면 너무 느리기 때문에 a la russe 방식을 쓰면 된다. '..

2482번: 색상환 풀이 원으로 계산하면 골치가 아파서 선형으로 만들어서 계산하고 나중에 원으로 만들어서 계산하면 된다. 조건 범위 내 모든 n에서 k=0일 땐 1이고(아무 것도 고르지 않는 것도 경우로 취급), k=1일 땐 n이다. n>1의 경우, n번째 색을 고르거나 안 고르는 두 가지 경우로 생각할 수 있는데 n번째 색을 고르면 n - 2개 중 k - 1개를 고른 것과 같고, n번째 색을 고르지 않으면 n - 1개 중 k를 고른 것과 같다. 다시 원으로 합칠 때는 양쪽 끝을 합친다고 생각하면 되기 때문에 선형의 양쪽 끝이 같은 경우를 생각해 줘야 한다. 양 끝에 색이 칠해져 있다면 이 경우는 불가능하므로 그걸 피하기 위해 양쪽 끝 중 하나를 잡아서 계산한다. 아까와 동일하게 n번째 색을 고르거나 안..

13302번: 리조트 풀이 dp[i][j] = j개의 쿠폰을 가지고 i일까지 있는데 드는 최소 비용. 처음에 쿠폰이 거슬렸는데 dp 배열을 2차원으로 두고 하니깐 한결 쉬워졌다. 재귀로 짰는데 for문으로도 짜보고 싶지만 잘 모르겠다. 코드 처음으로 3항 연산자의 감사함과 왜 있어야 하는가에 대해 진심으로 깨닫게 되었다... #include #include using namespace std; const int MN = 100 + 1; int N, M, dp[MN][MN / 2]; // dp[i][j]는 i일까지 j개 쿠폰 가지고 있는 최소 가격 수. bool chk[MN]; // 쉬는 날인지 확인 int f(int day, int coupon) { if (day > N) return 0; if (dp[..

1463번: 1로 만들기 풀이 스타트링크의 최백준님께서 유튜브에 올리신 DP 강좌를 발견했습니다. 필요하신 분은 보시기 바랍니다. 링크 동적 프로그래밍으로 풀 수 있다. X를 2로 나눌 때, 3으로 나눌 때, 1를 뺄 때의 최소값을 이전 값들을 이용해 계속 업데이트를 해주면 된다 다음 그림과 같이 N = 10일 때 1이 되기 까지의 대략적인 그림을 나타낸 것이다. 문제 해결 방식으로는 2가지가 있다. 10에서 9와 5의 가지를 내릴 수 있는데 사실 이 두 개로는 결과를 도출해 낼 수 없다. 그래서 어쩔 수 없이 각각에 또 다른 뿌리를 내려서 1까지 내려가 얼마나 연산을 해야 하는지 계산할 수 밖에 없다. 이것은 재귀함수로 구현할 수 있는 방식이다.(Top-down) 또 다른 방식으로는 아래서 위로 올라가..

2448번: 별찍기 - 11 풀이 분할&정복을 하면 된다. 큰 삼각형에서 3개로 삼분할 되는 프랙탈이 생기게 된다. 재귀함수를 사용해 삼분할에서 배열에 할당해주면 된다. 코드 #include #include int n; char arr[3072][6143]; void f(int n, int x, int y) { if (n == 3) { arr[y][x] = arr[y + 1][x - 1] = arr[y + 1][x + 1] = '*'; for (int i = 0; i > 1; f(dv, x, y); f(dv, x - dv, y + dv); f(dv, x + dv, y + dv); } int mai..

2523번: 별찍기 - 13 풀이 증가하는 삼각형 만들고 감소하는 삼각형 그려주면 된다. 코드 #include int main() { int n; scanf("%d", &n); for (int i = 0; i < n - 1; ++i, puts("")) { for (int j = 0; j = 0; --i, puts("")) { for (int j = 0; j

2447번: 별찍기 - 10 풀이 규칙성을 찾는 수 밖에 없는데 대개 한 칸 빈칸은 쉽게 찾을 수 있을텐데 큰 빈칸을 찾는 게 어려울 수 있다. 이것은 표를 그려보면 쉽게 알 수 있는데 n=9일 때를 그려보면 '나누기 3의 몫’이 1인 구간만 빈칸인 것을 알 수 있다. 코드 #include int n; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int dx = i, dy = j; while (dx) { if (dx % 3 == 1 && dy % 3 == 1) break; dx /= 3, dy /= 3; } putchar(dx ? ' ' : '*'); } puts(""); } return ..

1991번: 트리 순회 풀이 입력이 알파벳 순서대로 주어진다. 재귀 함수를 잘 이용한다!(재귀 함수 안 쓰면 굉장히 귀찮아짐) 코드 #include #include // hint: these alphabet inputs are inputed as increasing sequence struct Node { int mValue; int mNextLeft; int mNextRight; }; struct Node arr[26]; char root, left, right; void PrintPreorder(int c); void PrintInorder(int c); void PrintPostorder(int c); int main() { int N; for (int i = 0; i < 26; ++i) { arr..

1009번: 분산처리풀이를 해주면 된다. 하지만 long long형도 100^1000000까지는 저장하지 못하기 때문에 그리고 우리의 목적에만 두자면 굳이 a^b를 계산한 후 %10을 할 필요가 없고 연산 중간마다 %10 연산을 해주면 된다.또한 단순히 반복문을 돌려서 계산해도 되지만 제곱의 성질인 을 이용하면 훨씬 더 빠른 연산이 가능하다. 이 연산에 대한 설명은 여기를 눌러서 확인하길 바란다.코드1234567891011121314151617181920212223#include int pow(int a, int b){ int ans = 1; while (b) { if (b & 1) ans = (ans * a) % 10; a = (a * a) % 10; b >>= 1; } return ans;} int ..