안녕

0. 문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1. 풀이 방법 (참고로 해당 방법은 python3로는 안 풀립니다..ㅠ) 해당 문제를 푸는 로직은 간단합니다. 우선 그룹(인구 이동이 가능한 좌표들)을 찾고, 인구 이동하는 것을 반복합니다. 그렇게 모든 좌표에서 이동이 끝나면, 날짜를 하루 셉니다. 근데.....시간 초과가 나네요ㅠ.. 아마 중복으로 계산하는 부분이 있을 것으로 생각됩니다. 2. 코드 from co..

0. 문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. 풀이 방법 우선 0이 있다는 것은 +도 되고, -도 되므로 그냥 0이 n개 있으면, 0을 빼고 결과값에 2^n 만큼 곱해주며 된다. 아무튼 다른 숫자들은 2차원 배열을 만들어서 dp에 넣으면 된다. dp[가능한 숫자][현재까지 수행 횟수] 이런 식으로 하면, 최종적으로 원하는 숫자까지 가는데 만들 수 있는 등식의 수가 나온다. 항상 마지막에는 0의 개수만큼 2의 거듭제..

0. 문제 링크 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 방법 사실 해당 부분은 너무 어려워서 구글링을 하였다. https://hooongs.tistory.com/184 해당 블로그에서 설명을 잘 해놓았다.... 2. 코드 s1, s2 = input().strip(), input().strip() l1, l2 = len(s1), len(s2) dp = [[0] * (l2 + 1)..

0. 문제 링크 https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 1. 풀이 방법 문제에서 파악을 잘 해야 하는 것이, 전체 선택 -> 복사 -> 붙여넣기 과정은 한 번에 수행되어야 한다. 그리고 만약 buffer에 1보다 큰 값이 들어가있다면, 무조건 붙여넣기를 하는게 이득이다. 그러면 문제는 이제 어디서 전체..

0. 문제 링크 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 1. 풀이 방법 https://pacific-ocean.tistory.com/203 [백준] 2294번(python 파이썬) 문제 링크: https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 ..

0. 문제 링크 https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 1. 풀이 방법 일단 9, 3, 1로 때리는 순서는 순열을 이용해서 풀었다. 점화식을 얘기하자면 scv의 피가 1, 1, 1이라고 가정했을 때, 한 대만 때려도 된다. 그러면 피가 9, 3, 1 일 때는? 이때도 한 대만 때려도 된다. 결론적으로 피 i, j, k가 있을 때는 피가 i - 9, j - 3, k - 1 때보다 한 대만 더 때리면 된다는 뜻! (물론 순열을 이용해서 모든 경우의..

0. 문제 링크 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 1. 풀이 방법 보통 n * (m + 1)의 배열을 만들어서 처리하는 것 같은데, 나는 그러고 싶지 않았다. BFS와 흡사하지만 DP다. 따라서 m + 1을 n번 반복하는 식으로 풀었다. 최종적으로 n번 반복 후에 dp에 남아있는 값들 중 하나가 결과가 된다. 배열 대신에 check를 사용하여 이미 설정한 볼륨은 넣지 않았고, deque를 사용..

0. 문제 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 풀이 방법 코드에 모든 설명이 있음. 2. 코드 n, k = map(int, input().split()) board = [[b for b in map(int, input().split())] for _ in range(n)] w, v = [0] + [a for a, b in board], [0] + [b fo..

0. 문제 링크 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 1. 풀이 방법 만약 2~4까지 펠린드롬이라고 가정해보자. 그러면 1~5까지 펠린드롬인지는 어떻게 알 수 있을까? 바로 1번째와 5번째가 맞는지 비교하고, 2~4가 펠린드롬인지 확인하면 되는 것이다. 따라서 n~m까지 펠린드롬인지 확인하기 위해서는, n-1~m-1이 펠린드롬인지 확인하고, n번째와 m번째가 펠린드롬인지 확인하면 된다. 숫자가 하나만 있는 경우는 무조건 펠린드롬이고, 2개가 있는 경우에는 맞는지 확인만 하..

0. 문제 링크 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 1. 풀이 방법 i에서 j로 가는데, 기존에 점프한 횟수보다 i + 1이 더 적으면 가면 된다. dp 배열은 inf로 초기화 해야 한다. 이런 식으로 모든 i에 대해서, 점프할 수 있는 j를 찾아가며 초기화를 하면 결국 최소 횟수가 나오게 된다. 2. 코드 import sys n = int(sys.stdin.readline().strip()) board = [b for ..