개발 일지

문제 1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 어떤 시점 i에서 고를 수 있는 색은 총 세가지가 있으므로, 세 가지 색에 대해서 비용이 최소가 되게끔 dp를 작성하면 된다. N = int(input()) rgb = [[]] for _ in range(N): rgb.append(list(map(int,input().split()))) dp = [[0]*3 for _ in range(N+1)] for i in range(1,N+1)..

문제 1912번: 연속합 (acmicpc.net) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 적분으로 생각하면 좀 더 쉽게 접근 가능하다. 회색이 입력으로 주어지는 값들의 그래프, 노란색이 적분 그래프, 주황색이 dp 그래프이다. 구간합은 적분그래프에서 F(x) - F(x-1) 와 같기 때문에 F(x)가 0 이하인 시점부터는 구간합을 적분값이 아닌 원래 그래프 값 f(x)로 정해주면 된다. 그림이 살짝 잘못됐는데, F(x) = 0 이 되는 시점부터 주황색선은 y(x)를 따라가다가 y(x)가 0 이상이 되는 시..

문제 Softeer Softeer 문제에서 주어진 조건을 만족하는 서로 다른 (i, j, k) 순서쌍의 개수를 출력한다. 첫 번째 위치에는 2번 버스, 두 번째 위치에는 3번 버스, 그리고 세 번째 위치에는 1번 버스가 기다 softeer.ai 풀이 Softeer Softeer 안녕하세요. Softeer 운영 담당자 입니다. 지난 9월 6일에 Softeer 4회 정기 인증평가가 실시되었습니다. 이번 역량 진단에도 많은 분들께서 관심을 가지고 참여하여 주셨습니다. 인증을 받으신 분들 softeer.ai 도저히 풀 수 없어 풀이를 봤다. 결국 DP 문제였는데, 버스 번호가 1 부터 N까지 자연수로 정해져 있다는 점에 착안하여 어떤 버스 번호 X와 주어진 배열 A 에서의 인덱스 j 에 대해서 dp[X][j] ..

문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 5,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 우선, 제한사항의 경우의수를 10^9..

문제 14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 1 테이블과 같이 소요시간과 보상이 주어졌을 때, 각 업무를 조합하여 경우들 중 최대값을 찾아내야 하는 문제이다. 가장 먼저, 조합의 경우를 찾는 방법을 바로 알아채기가 힘드니 주어진 예시를 가시화하여 상황을 정리해본다. 아래는 예시를 가시화하여 나타낸 그림이다. 위와 같은 업무 테이블을 이용해 7일차 까지 조합의 경우의 수 중 가장 큰 값을 찾아내야한다. 1일차 업무를 하고 받는 보상과 4일차 이후 부터의 조합 중 보상의 최대값을 더한 경우, 1일차 업무를 포기하고 2일차 혹은 3일차 업무를 하는 경우로 나뉜다. 이와 같은식으로 f(i)를 i일..