[[TableOfContents]] === ë¬¸ì œ === * [https://www.acmicpc.net/problem/1402 아무래ë„ì´ë¬¸ì œëŠ”A번난ì´ë„ì¸ê²ƒê°™ë‹¤] * [https://www.acmicpc.net/problem/15645 ë‚´ë ¤ê°€ê¸° 2] * [https://www.acmicpc.net/problem/6064 카잉 ë‹¬ë ¥] * [https://www.acmicpc.net/problem/2606 ë°”ì´ëŸ¬ìФ] * [https://www.acmicpc.net/problem/6198 ì˜¥ìƒ ì •ì› ê¾¸ë¯¸ê¸°] * [https://www.acmicpc.net/problem/7579 앱] * [https://www.acmicpc.net/problem/13239 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; } }}} ==== 카잉 ë‹¬ë ¥ ==== [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) }}} ==== ë°”ì´ëŸ¬ìФ ==== 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; } }}} ==== ì˜¥ìƒ ì •ì› ê¾¸ë¯¸ê¸° ==== 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 }}} {{{ #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; } }}} ----------------------------------- [알얼알]