링크 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 소요시간:25분 실패 설계하기(접근방법) 1. 입력받기 전깃줄 리스트를 입력받는다 2. 구현하기 현재 왼쪽 전깃줄을 기준으로 그 전 전깃줄 중 최대값을 가져오면 될 것 같았는데 어떻게 우측 값을 조절해야하는지 떠올리질 못했다 현재 전깃줄을 기준으로 첫 전깃줄 부터 최대값을 비교한다 그 중 현재 전깃줄의 우측 값보다 작은 값들로만 비교한다 우측 값이 현재보다 작다면 비교하는 전깃줄의 dp(이..
링크 : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 소요시간: 30분(참고) 설계하기(접근방법) 1. 입력받기 행렬을 일력받는다 2. 구현하기 이 문제는 dfs와 dp를 섞은 문제이다 행렬이 커져서 dfs를 전부 탐색하게 된다면 시간초과가 날 것이다 그래서 시간 초과를 줄이기 위해서는 이미 갔던 길에 대해서 메모이제이션을 할 필요가 있다 또 다른 dfs를 할 때 이미 탐색이 전부 완료된 갔던 길을 만났고 그 길에 대해서 다시 탐색할 필요가..
링크 : https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 소요시간: 24분 30초 설계하기(접근방법) 1. 입력받기 회의 리스트를 입력받는다 2. 구현하기 dp를 구현 할 때 dp[현재 날짜 + 상담 소요날짜]의 날의 돈이 현재 날짜의 돈 + 상담 돈보다 작으면 갱신해준다 주의해야 하는점은, 우리는 회의를 미래를 위해서 하지 않을 수도 있다 즉 dp 값을 갱신할 때 항상 이전의 최대값으로 갱신을 해준 다음 d..
링크 : https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 소요시간: 24분 22초 설계하기(접근방법) 1. 입력받기 2. 구현하기 가장 긴 증가하는 부분수열을 거꾸로 하면 된다 가장 긴 감소하는 부분수열 = 가장 긴 증가하는 부분 수열을 뒤집은 것이고 우리는 수열의 길이를 구하면 되기 때문에 뒤집어서 풀어도 된다 리스트를 뒤집은 후 앞에서 부터 dp를 해준다 현재 ..
링크 : https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 소요시간: 30분 실패 설계하기(접근방법) 1. 입력받기 n 을 입력받는다 2. 구현하기 가로가 2인 직사각형은 쉽게 구할 수 있다 총 3가지가 나온다 가로가 4인 직사각형까지 구했지만 사실 6..8...10 쭉쭉 직사각형이 하나씩 들어난다 점화식이 처음에 어려웠는데 그림을 그려보니 이해가 되었다 dp[2] = 3 dp[4] = dp[2] * 3 + (4짜리 직사각형 2가지 케이스) dp[6] = dp[4] * 3 + dp[2]에다가 4짜리 직사각형 -> dp[2] * 2 + 6짜리 직사각형 ..
링크 : https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 문제 소요시간: 23분 9초 설계하기(접근방법) 1. 입력받기 코인을 입력받는다 2. 구현하기 이전에 풀어본 dp 문제이다 이전 문제와 다른 점은 동전이 정해지지 않았다는 점이다 하지만 set으로 중복되는 동전을 한정짓고 while문으로 작은 동전부터 dp[n] = dp[n-1] + 1 을 반복한다면 최적의 해를 구할 수 있다 이전 동전 0 문제를 참고하자..
링크 : https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 문제 소요시간: 1시간 40분 설계하기(접근방법) 1. 입력받기 2. 구현하기 코드 참고 3. 출력하기 코드(출력) import sys input = sys.stdin.readline n, trial = map(int,input().split()) water = [list(map(int, input().split())) for _ in range(n)] cloud_loc = [[0..
링크 : https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제 소요시간: 50분 38초 설계하기(접근방법) 1. 입력받기 톱니의 상태와 회전할 톱니번호, 회전 방향을 입력받는다 2. 구현하기 톱니 문제는 rotate를 해야하기 때문에 deque의 자료구조를 사용하는 것이 좋다 톱니 4개를 덱으로 선언을 해준다 그 후 각각의 톱니가 맞물려있는 지점의 상태를 저장해 준다 톱니 1,2,3,4 에 대해서 각각 로직이 꼬이지 않도록 회전 순서를 정..
