D cron

문제 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 왜 틀렸을까? 이 문제에 어떻게 DP를 적용할지 생각이 나지 않았다. 그리고 다른사람의 풀이도 보고 설명도 많이 들었지만 과정이 명확하게 이해가 되지 않았다. 나처럼 동전이 도저히 이해가 되지 않았던 사람을 위해 최대한 친절하게 풀어서 설명해보려고 한다. 문제 풀이 방식 많은 분들이 1차원 dp를 사용해서 풀었는데, 나는 1차원 dp table를 사용하는 방식으로는 이해가 잘..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 왜 틀렸을까? 이 문제를 풀기 전에는 이차원 배열에서 0과 1을 통해 board[1][3] 이면 1에서 3을 갈 수 있다는 식으로 연결 상태를 나타냈었는데, 이 문제는 노드의 개수가 최대 100,000개 이므로 이차원 배열에서 연결상태를 표시하게 되면 10만*10만 = 100억개의 칸을 사용하기 때문에 메모리 초과가 날 수 밖에 없다. # 원래 알던 이차원배열에 모두 저장하는 방식 board = [[0]*(n+1) for i in range(n+1)] f..

문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 왜 틀렸을까? 시간초과로 엄청 고생했던 문제였다. 시간초과를 줄여보기 위해서 바이러스가 우리가 구하고자 하는 좌표칸 안에 증식되게 되면 변하지 않는 점을 이용해서 우리가 구하고자 하는 위치에 바이러스가 증식되는 순간 종료시키는 코드를 추가했다. 처음 짰던 코드에서는 바이러스의 종류별로(1~K 까지) 모두 확인하면서 코드를 짰었는데, 그 시간을 줄이기 위해서 전체..