알얼알/0514 - ZeroWiki

2.1. 아무래도이문제는A번난이도인것같다
2.2. 내려가기 2
2.3. 카잉 달력
2.4. 바이러스
2.5. 옥상 정원 꾸미기
2.6. 앱
2.7. Combinations

1. 문제 ¶

아무래도이문제는A번난이도인것같다(https://www.acmicpc.net/problem/1402)
내려가기 2(https://www.acmicpc.net/problem/15645)
카잉 달력(https://www.acmicpc.net/problem/6064)
바이러스(https://www.acmicpc.net/problem/2606)
옥상 정원 꾸미기(https://www.acmicpc.net/problem/6198)
앱(https://www.acmicpc.net/problem/7579)
Combinations(https://www.acmicpc.net/problem/13239)

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(N²) 입니다.
DFS와 BFS는 전형적인 방식으로 구현하면 되니 코드는 생략하겠습니다.

아래는 플로이드 워셜 알고리즘으로 구현한 코드입니다.
1번 정점만이 아니라 모든 정점을 대상으로 탐색하기 때문에 O(N³) 입니다.
시간복잡도는 비효율적이지만 이 문제는 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. 옥상 정원 꾸미기 ¶

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

_nC_k = _n-1C_k + _n-1C_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

#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;
}

알얼알

Contents