안녕

0. 문제 링크 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 1. 풀이 방법 첫 번째로 동전의 위치를 찾았다. 만약 동전이 둘 다 범위 안에 있다면, 무난하게 동전을 움직이게 했고, 만약 벽이라면 움직이지 않고 다시 현재 위치에 있게 했다. 그리고 다시 deque에 넣었다. 만약 동전이 둘 다 범위 바깥이라면, 둘 다 떨어졌다는 의미이므로, continue를 했다. 만약 한 개만 떨어졌다면 그대로 반환을 했음 하지만 해당 경우에 동전이 겹..

0. 문제 링크 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 1. 풀이 방법 우선 배열을 돌린다, 회전한다 뭐 이런거는 너무 오래 걸릴 것 같았다. 그래서 12시 방향을 시작점으로 하고, 그 좌표를 저장하는게 좋아보였다. 그래서 결국엔 다 풀었는데, 뭔가 마지막 예제가 계속 안 됐었다. 알고보니까 인접한 모든 애들을 없애야 하는 것이 있었다. 여기서 다시 BFS로 풀자니 푼 시간이 아깝고, 다시 구현하기도 귀찮았다. 그래서 ..

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 때보다 한 대만 더 때리면 된다는 뜻! (물론 순열을 이용해서 모든 경우의..