안녕

0. 문제 링크 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 1. 풀이 방법 딱히 어려운 점은 없었음 클래스를 이용해서 각 말에 대한 인스턴스를 생성하여 처리하였음 굳이 클래스를 이용하지 않아도 될 것 같은데, 뭔가 클래스로 하는게 직관적일 것 같았음 클래스를 쓰지 않았으면 코드를 더 줄일 수 있었을 듯, 그래도 더 직관적임 2. 코드 from collections import deque class Chess: def __init__(sel..

0. 문제 링크 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1. 풀이 방법 사실 구현은 그냥 하라는 대로 하면 돼서 크게 어렵지는 않은 것 같다. 먼지를 분산시키고, 이후에 바람을 불었다. 다만 바람을 부는 과정이 조금 쉽지 않았는데, 방향을 전환하면서, 현재 값은 이전 값이 저장된 변수로 대체하고, 현재 값을 변수에 넣는 과정을 반복하면 해결되었다. 2. 코드 r, c, t = map(int, input().split()) maps =..

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..