BLUE DOLPHIN

[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..

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) 또 다른 방식으로는 아래서 위로 올라가..