https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net - 앞서 포스팅한 동전 문제와 같은 dp문제이다. https://kcw0360.tistory.com/4 [BAEKJOON] 9084 동전 - Python 9084번: 동전 (acmicpc.net) 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. kcw0..
https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net - 남아있는 얼음의 합, 가장 큰 덩어리가 차지하는 칸의 수를 구하는 구현문제였다. - 조건에 따라 차례대로 구현을 진행했다. - 회전하는 부분이 헷갈렸다. for문 말고 딱히 어떻게 표현해야 할지 몰라서... - 그 이외에는 특별한게 없었고 얼음 덩어리 찾는 곳에서는 BFS를 사용하여 덩어리를 찾았고 max로 갱신하면서 진행했다. import sys input = sys.st..
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net - 조건도 난도가 높거나 복잡하게 주어진 것이 아니었기 때문에 크게 어려움은 없었던 것 같다. - 토네이도의 이동(방향)과 조건대로 흩날리는 모래(그림)가 전부였던 문제 import sys input = sys.stdin.readline N = int(input()) sand = [list(map(int, input().split())) for _ in range(..
https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net - 어디가 틀렸는지 몰라서 헤맨 탓에 3시간 넘게 걸렸다. 단계 별로 조건에 맞는 값이 나오는지 확인 후 넘어가는 습관을 들이자. - 2차원 리스트를 이용하여 풀이를 진행했지만, 이전에 포스팅했던 파이어볼 문제처럼 dict를 이용한다면 제출 시 시간을 더 단축할 수 있을 것이다. 코드를 참고하고 싶다면 해당 문제에서 맞힌사람 → 언어: Python에서 2등이신 분..
https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net - 특별한 알고리즘이 필요하지 않았지만 틀린 부분 찾느라 시간을 많이 소비했다. - 문제에서 주어진 조건을 순서대로 구현하면 된다. - 채우는 것을 매번해줘야 하기 때문에 미리 좌표를 구해놓고 시작했다. 상어를 기준으로 문제에서 주어진 달팽이 형태의 이동경로를 따라 좌표를 list에 넣어주었다. - 먼저 블리자드로 구슬 파괴를 하는데 이때 파괴도 폭파에 포함인 줄 알고 같이 카운..
21610번: 마법사 상어와 비바라기 (acmicpc.net) 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net - 구현문제로 조건에 따라 순서대로만 한다면 큰 문제없이 풀리는 문제다. - 구름 생성에서 구름이 소멸한 자리인지 체크하기 위해 in 연산자를 사용했는데, 해당 문제에서는 중복되는 구름의 좌표가 없기 때문에 set을 이용했다. in 연산자는 list에서 시간복잡도는 O(n)이지만 set에서는 O(1)이기 때문에 조금이라도 시간을 줄여보고자 set을 이용했다. import sys input = s..
20056번: 마법사 상어와 파이어볼 (acmicpc.net) 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net - 2차원 배열로 진행하면서 헤매다가 fireball의 정보의 좌표를 key, 좌표에 있는 파이어볼 정보를 list로 만들어 풀었더니 쉽게 구현이 가능했다. - '행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.'는 파이어볼이 이동시 행 또는 열의 좌표가 N-1번, N번, 1번, 2번 이런 식..
21608번: 상어 초등학교 (acmicpc.net) 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net - 삼성 기출문제는 주로 구현 문제에 코드가 길어서 헷갈리지 않게 주석을 달거나 메모해 가면서 진행하는 게 좋은 것 같다. - |r1 - r2| + |c1 - c2| = 1 => 인접한 칸(상하좌우) - dict에 학생 번호(key), 좋아하는 학생 번호(value)로 받아 정리한다. ※ Python 3.6 버전부터는 dict에 순서를 가지고 있다. 대부분 코딩테스트에서 Python 3.6 버전 이상..
9084번: 동전 (acmicpc.net) 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net - 각각의 동전들이 1 ~ m원까지 만들 수 있는 곳의 경우의 수를 구한다. - i-coin을 만드는 값이 존재하는 경우 - dp[i] = dp[i] + dp[i-coin] - 존재하지 않는 경우는 그대로 유지 import sys input = sys.stdin.readline T = int(input()) for _ in range(T): n = int(input()) # 동전의 가지수 coins = ..
