U E D R , A S I H C RSS
ZeroWiki

알얼알/0514

Difference between r1.3 and the current

@@ -22,9 +22,9 @@
{{{
dp[i][j] : i번째 단계에 j번째 칸에 도착하는 경우의 최대값

dp[i][1] = MAX(dp[i-1][1], dp[i-1][2]) + val[i][1]
dp[i][2] = MAX(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + val[i][2]
dp[i][3] = MAX(dp[i-1][2], dp[i-1][3]) + val[i][3]
dp[i][1] = MAX(dp[i-1][1], dp[i-1][2]) + arr[i][1]
dp[i][2] = MAX(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + arr[i][2]
dp[i][3] = MAX(dp[i-1][2], dp[i-1][3]) + arr[i][3]

최소값은 MAX를 MIN으로 바꾸고 똑같이 하면 됨.
}}}
@@ -144,11 +144,57 @@
==== 옥상 정원 꾸미기 ====
attachment:ex.png

==== 앱 ====
0-1 knapsack 배낭 문제 응용.
배낭 문제에 대해 학습해보는걸 추천합니다.
자세한 해설은 정올 교재를 참고하세요~
{{{
dp[i][j] = MAX(dp[i-1][j], dp[i-1][j-cost[i]] + memsize[i])
}}}
 
{{{
#include <iostream>
#define MAX(x,y) ((x)>(y)?(x):(y))
using namespace std;
 
int dp[100][10001];
int memsize[100];
int cost[100];
 
int main() {
int N, M;
cin >> N >> M;
for (int i = 0; i < N; i++) cin >> memsize[i];
for (int i = 0; i < N; i++) cin >> cost[i];
 
for (int i = cost[0]; i <= 10000; i++)
dp[0][i] = memsize[0];
 
for (int i = 1; i < N; i++) {
for (int j = 1; j <= 10000; j++) {
if (j - cost[i] >= 0)
dp[i][j] = MAX(dp[i-1][j], dp[i-1][j-cost[i]] + memsize[i]);
else
dp[i][j] = dp[i-1][j];
}
}
 
for (int i = 1; i <= 10000; i++) {
if (dp[N-1][i] >= M) {
cout << i;
return 0;
}
}
}
}}}
==== Combinations ====
,,n,,C,,k,, = ,,n-1,,C,,k,, + ,,n-1,,C,,k-1,, 공식을 사용합시다.
또한 (A+B)%C = ((A%C)+(B%C))%C,
(A*B)%C = ((A%C)*(B%C))%C 라는 모듈러 분배법칙도 알고 있어야 합니다.
주의할 점은 모듈러 분배법칙이 나눗셈에 대해선 성립하지 않습니다!
시간복잡도는 O(NK) 입니다.
자세한 해설은 정올 교재를 참고하세요~
{{{
dp[n][k] = (dp[n-1][k] + dp[n-1][k-1]) % MOD
}}}

1. 문제

2. 해설

2.1. 아무래도이문제는A번난이도인것같다

N = N * (-1) * (-1) * (-1) * (-1) * ... 으로 음의 무한대까지 만들고
N = N * 1 * 1 * 1 * 1 * ... 으로 양의 무한대까지 만들 수 있다.
print('yes\n'*int(input()))

2.2. 내려가기 2

다이나믹 프로그래밍으로 풀립니다.
시간 복잡도는 O(n)
dp[i][j] : i번째 단계에 j번째 칸에 도착하는 경우의 최대값

dp[i][1] = MAX(dp[i-1][1], dp[i-1][2]) + arr[i][1]
dp[i][2] = MAX(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + arr[i][2]
dp[i][3] = MAX(dp[i-1][2], dp[i-1][3]) + arr[i][3]

최소값은 MAX를 MIN으로 바꾸고 똑같이 하면 됨.


#include <iostream>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX3(x,y,z) MAX(MAX(x,y),z)
#define MIN3(x,y,z) MIN(MIN(x,y),z)
using namespace std;

int arr[100001][4];
int dp[100001][4][2];

int main() {
  int N;
  cin >> N;

  for (int i = 1; i <= N; i++)
    cin >> arr[i][1] >> arr[i][2] >> arr[i][3];

  for (int i = 1; i <= N; i++) {
    dp[i][1][0] = MIN(dp[i-1][1][0], dp[i-1][2][0]) + arr[i][1];
    dp[i][2][0] = MIN3(dp[i-1][1][0], dp[i-1][2][0], dp[i-1][3][0]) + arr[i][2];
    dp[i][3][0] = MIN(dp[i-1][2][0], dp[i-1][3][0]) + arr[i][3];
    dp[i][1][1] = MAX(dp[i-1][1][1], dp[i-1][2][1]) + arr[i][1];
    dp[i][2][1] = MAX3(dp[i-1][1][1], dp[i-1][2][1], dp[i-1][3][1]) + arr[i][2];
    dp[i][3][1] = MAX(dp[i-1][2][1], dp[i-1][3][1]) + arr[i][3];
  }

  cout << MAX3(dp[N][1][1], dp[N][2][1], dp[N][3][1]) << ' ';
  cout << MIN3(dp[N][1][0], dp[N][2][0], dp[N][3][0]);
  return 0;
}

2.3. 카잉 달력

http://andamiro25.tistory.com/93
http://sexycoder.tistory.com/26
http://tastyprogramming.tistory.com/65
for _ in range(int(input())):
  m,n,x,y=map(int,input().split())
  if not (1<=x<=m and 1<=y<=n):
    print(-1)
    continue

  if m<n:
    m,n=n,m
    x,y=y,x

  i=x
  if x<=n:
    j=x
  else:
    j=(x-1)%n+1

  ans,first_j=i,j
  while i-j!=x-y:
    j+=m-n
    if j>n:
      j=(j-1)%n+1
    if j==first_j:
      ans=-1
      break
    ans+=m

  print(ans)

2.4. 바이러스

1번 정점에서 DFS 또는 BFS를 돌려서 탐색한 정점의 수를 구하면 되는 문제입니다.
BFS를 추천합니다. DFS는 재귀를 써서 터지기 쉽습니다.
시간복잡도는 넉넉히 잡아 O(N2) 입니다.
DFS와 BFS는 전형적인 방식으로 구현하면 되니 코드는 생략하겠습니다.

아래는 플로이드 워셜 알고리즘으로 구현한 코드입니다.
1번 정점만이 아니라 모든 정점을 대상으로 탐색하기 때문에 O(N3) 입니다.
시간복잡도는 비효율적이지만 이 문제는 N 최대값이 100이라 터지지 않습니다.
거기에다 코드도 간결해서 좋습니다.
#include <iostream>
using namespace std;

bool connect[101][101];

int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    connect[x][y] = true;
    connect[y][x] = true;
  }

  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      for (int k = 1; k <= N; k++) {
        if (connect[j][i] && connect[i][k]) {
          connect[j][k] = true;
          connect[k][j] = true;
        }
      }
    }
  }

  int ans = 0;
  for (int i = 2; i <= N; i++)
    if (connect[1][i]) ans++;
  cout << ans;
  return 0;
}

2.5. 옥상 정원 꾸미기

ex.png
[PNG image (370.67 KB)]


2.6. 앱

0-1 knapsack 배낭 문제 응용.
배낭 문제에 대해 학습해보는걸 추천합니다.
자세한 해설은 정올 교재를 참고하세요~
dp[i][j] = MAX(dp[i-1][j], dp[i-1][j-cost[i]] + memsize[i])


#include <iostream>
#define MAX(x,y) ((x)>(y)?(x):(y))
using namespace std;

int dp[100][10001];
int memsize[100];
int cost[100];

int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 0; i < N; i++) cin >> memsize[i];
  for (int i = 0; i < N; i++) cin >> cost[i];

  for (int i = cost[0]; i <= 10000; i++)
    dp[0][i] = memsize[0];

  for (int i = 1; i < N; i++) {
    for (int j = 1; j <= 10000; j++) {
      if (j - cost[i] >= 0)
        dp[i][j] = MAX(dp[i-1][j], dp[i-1][j-cost[i]] + memsize[i]);
      else
        dp[i][j] = dp[i-1][j];
    }
  }

  for (int i = 1; i <= 10000; i++) {
    if (dp[N-1][i] >= M) {
      cout << i;
      return 0;
    }
  }
}

2.7. Combinations

nCk = n-1Ck + n-1Ck-1 공식을 사용합시다.
또한 (A+B)%C = ((A%C)+(B%C))%C,
(A*B)%C = ((A%C)*(B%C))%C 라는 모듈러 분배법칙도 알고 있어야 합니다.
주의할 점은 모듈러 분배법칙이 나눗셈에 대해선 성립하지 않습니다!
시간복잡도는 O(NK) 입니다.
자세한 해설은 정올 교재를 참고하세요~
dp[n][k] = (dp[n-1][k] + dp[n-1][k-1]) % MOD


#include <iostream>
using namespace std;

int dp[1001][1001];

int main() {
  dp[0][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    dp[i][0] = 1;
    for (int j = 1; j <= i; j++)
      dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % 1000000007;
  }

  int T;
  cin >> T;
  for (int i = 0; i < T; i++) {
    int a, b;
    cin >> a >> b;
    cout << dp[a][b] << '\n';
  }

  return 0;
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:30:22
Processing time 0.1153 sec