개발 일지

문제 10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 dp[i][j] 에 대해서, 길이가 i 일 때 맨 뒤 숫자가 j 일 경우 가능한 계단 수를 목표로 점화식을 작성한다. N = int(input()) dp = [[0]*101 for _ in range(N+1)] for i in range(1,10): dp[1][i] = 1 for i in range(2,N+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][j+1] elif j == 9: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = (dp[i..

문제 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 예를 들어 X가 6인 경우, dp[6] = min(dp[5],dp[3],dp[2]) + 1이 될 것이다. 즉 X가 2로 나눠지는 경우와 3으로 나눠지는 경우에 대해서 점화식을 세우면 된다. N = int(input()) dp = [0]*(10**6+1) dp[1],dp[2],dp[3] = 0,1,1 for i in range(4,N+1): dp[i] = dp[i-1] + 1 if i%2 == 0: dp[i] = min(dp[i], dp[i//2]+1) if i%3 == 0: dp[i] = min(dp[i], dp[i..

문제 2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 N 번째 계단을 반드시 밟으면서 계단 값들의 합이 최대가 되는 경우는, N-3번째 계단과 N-1번째 계단을 밟는 경우가 있고 N-2번째 계단만 밟는 경우가 있다. 조건에 의해 3번 연속 계단을 밟을 수 없기 때문이다. N = int(input()) stairs = [0]*10001 for i in range(1,N+1): stairs[i] = int(input()) dp = [0]*10001 dp[1] = stai..

문제 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] ..

문제 17822번: 원판 돌리기 (acmicpc.net) 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 간단한 구현 문제지만, 각 행이 큐로 되어있어 인접 노드를 탐색할 때 주의해야한다. 어이없게도 "배수"를 반복문을 통해 2배씩 곱해주는 것으로 계산해서 많은 시간을 날렸다. 또한 평균을 구할 때 cnt 가 0이 되는 때도 있음을 주의해야한다. from collections import deque N,M,T = map(int,input().split()) # 0:W 1:R 2:B circ..

문제 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 사다리 조작 문제와 동일한 조합 문제이다. 치킨집을 최대 M개 까지 남길 수 있고, M개 이하의 가능한 조합을 짜보면서 최소가 되는 도시 치킨 거리를 갱신한다. 치킨집은 최대 13개, 가정집은 최대 2N개 까지만 존재할 수 있으므로 따로 좌표를 리스트에 넣어놓고 1차원 리스트에 대해 조합을 짜도 된다. N,M = map(int,input().split()) board = [[0]*(..

문제 Softeer Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 정말 오랜만에 c++로 풀이하느라 애를 많이 먹었다. 문제 자체는 정말 쉬운데, 회의실 이름을 키 값으로 하고 스케쥴 상 비어있는 시간을 pair로 가지고 있는 vector를 값으로 map을 만들어준뒤, 예약 시간이 입력될 때마다 해당 회의실의 가능한 시간을 갱신해나가면 된다. 새로 vector를 만들어서 pair를 넣어줘서 map의 value가 새로 생성된 pair를 가리키게 하면 되겠다. 다만 c++은 사용하지 않는 vector는 메모리 해제를 직접 해줘야 하는데, 파이썬의 편리함에 물들어 까먹고 그냥 제출해버렸다... 어쨌거나 맞았으니 다행. 다음은 문제를 풀며 참고한 c++ 문법 레퍼런스이..

문제 Softeer Softeer 자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 직진만 가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로 softeer.ai 풀이 N만큼 반복문을 돌며 교차로에 새로 들어서는 차량의 도착 시간 및 방향을 입력받아 입력된 차량들이 교차로를 지나간 시간이 어떻게 되는지 출력하는 문제이다. 따라서 시간의 흐름에 따라 교통상황이 어떻게 흘러가는지 면밀하게 살펴 문제에 접근할 필요가 있다. 시간의 흐름을 구현하는것이 핵심이며, 새로 차량 정보가 입력되면 그 이전 시점까지의 교통 상황을 정리하면 된다. 1초 동안, 만약 차량들이 서로 마주보고 있다면 동시에 지나갈수 있고 그렇지 않다면 오직 하나의 차량만 지나갈 수 있다..