링크 : https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 소요시간: 16분 50초 설계하기(접근방법) 1. 입력받기 n을 입력받는다 2. 구현하기 이친수를 써보니 피보나치 수열의 형태가 나타났다 왜 dp[n] = dp[n-1] + dp[n-2]의 형태가 나타날까??? 새로운 이친수를 구할 때 우리는 끝이 0 아니면 1인 케이스로 나눌 수 있다 끝이 0인 케이스는 dp[n-1]의 케이스에서 어느곳이든 0을 붙일 수 있기 때문에 d..
링크 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 소요시간: 1시간 25분 설계하기(접근방법) 1. 입력받기 2. 구현하기 접근법으로 알아낸 것이 아닌 수열을 그려보며 알게 되었다. n과 k 의 형태는 0이 없는 경우에는 k가 n 미만일 때는 파스칼의 삼각형 형태를 보인다 n = 5, k = 3일 때는 1 1 3 / 1 3 1 / 3 1 1 1 2 2/ 2 1 2/ 2 1 1 로 6개다 여기서 0이 추가된다면 어떻게 될까? 각 수열의 자리에 0 이 들어가는 경우를 생각하면 k = 1일 때에다가 0을 2개 추가한 수열 k = 2일 때에다가 0을 1개 추가한 수..
링크 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 소요시간: 18분 12초 설계하기(접근방법) 1. 입력받기 배열을 입력받는다 2. 구현하기 이 문제의 핵심 포인트는 가장 긴 산을 만드는 것이다 산이라고 하면 4 3 2 2 1 1 와 같은 형태일 것이다 가장 긴 증가하는 부분 수열은 쉽게 구할 수 있다 dp를 선언하여 현재 자신의 값보다 작은 값 중 dp의 길이가 최대값이었던 dp에 +1을 해주면 된다 같은 방식으로 가장 긴 감소하는 부분 수열도 쉽게..
링크 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 소요시간: 20분 32초 설계하기(접근방법) 1. 입력받기 트럭 수, 다리 길이, 하중을 입력받는다 2. 구현하기 q를 2개 구현하면 문제를 상당히 쉽게 풀 수 있다 bridge와 truck_order을 덱으로 구현한다 그 후 다리의 하중이 (들어갈 트럭의 무게 + 다리에 있는 트럭들의 무게 합) 을 버틸 수 있다면 다의[-1]번을 새..
링크 : https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 문제 소요시간: 19분 11초 설계하기(접근방법) 1. 입력받기 후보 추천 리스트를 입력받는다 2. 구현하기 먼저 리스트 내에 현재 추천하는 후보가 있는지 검사한다 만약 있다면 추천수를 1 증가시킨다 만약 없다면 -> 리스트에 자리가 아직 남아있으면 append 해준다 만약 자리가 없다면 추천수가 적고 가장 오래된 후보를 del 해준다 매 회차에 추천수와 추천된 순서를 기준으로 ..
링크 : https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 문제 소요시간: 1시간 30분 설계하기(접근방법) 1. 입력받기 이닝별 타자의 결과를 입력받는다 2. 구현하기 타순은 4번째 타자를 1번으로 고정을 하고 permutations로 base를 구현하는 것이 까다로웠다 3. 출력하기 코드(출력) import sys from itertools import permutations input = sys.stdin.readline def find_scor..
링크 : https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 문제 소요시간: 2시간 실패 설계하기(접근방법) 1. 입력받기 목표 채널과 고장난 번호가 없으면 입력을 받지 말고 있으면 입력받는다 2. 구현하기 0 부터 1000000 즉 7자리 수까지 숫자를 모두 검사를 한다 고장난 번호가 있는 숫자는 제외하여 숫자를 눌러야 하는 횟수와 +- 버튼을 눌러야 하는 횟수(숫자의 차이) 를 더한 값중 최소를 출력한다 3. 출력하기 최소를 ..
링크 : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 소요시간: 34분 47초 설계하기(접근방법) 1. 입력받기 배열을 입력받는다 2. 구현하기 먼저 배열을 정렬해준다 그래야 가장 큰값과 가장 작은 값을 더하면서 비교할 수 있다 최소값은 sys.maxsize로 선언해준다 그 후 양 끝을 p1 = 시작점 index = 0 p2 = 끝점 index = n - 1 로 잡는다 그 둘을 더해본다 그것의 절대값과..
