알얼알/0514

문제

• 아무래도이문제는A번난이도인것같다
• 내려가기 2
• 카잉 달력
• 바이러스
• 옥상 정원 꾸미기
• 앱
• Combinations

해설

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

N = N * (-1) * (-1) * (-1) * (-1) * ... 으로 음의 무한대까지 만들고 N = N * 1 * 1 * 1 * 1 * ... 으로 양의 무한대까지 만들 수 있다.

print('yes\n'*int(input()))

내려가기 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;
}

카잉 달력

[1] [2] [3]

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)

바이러스

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

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

옥상 정원 꾸미기

앱

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

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

---

알얼알