free from

문제소개 2806 DNA 발견은 DP 문제 입니다. 개인적으로는 DP를 좋아합니다. 점화식 세우거나 규칙을 찾는게 재밌습니다 ㅎㅎ;; 보통 메모제이션할 배열을 하나만 생각하는데 익숙한데 해당 문제는 A와 B에 대한 메모제이션을 생각하면 쉽게 풀 수 있습니다. 문제해결 DNA의 돌연변이 규칙이 점화식 세우는데 단서가 됩니다. 1) DNA에서 1개만 바꿀 수 있다. 2) 1번 부터 K번까지 한번에 바꿀 수 있다. A[i] = 1번 부터 i번까지 A로 만드는 최소 돌연변이 횟수 B[i] = 1번 부터 i번까지 B로 만드는 최소 돌연변이 횟수라고 하면 A[i] = A[i-1] 또는 B[i -1] + 1 (2번 규칙을 적용) 이 된다는 것을 찾을 수 있습니다. 소스보기

문제소개 1669 멍멍이 쓰다듬기는 수학 문제입니다. 계산 과정에서 2,147,483,648만큼 큰 값이 나올 수 있으므로 유의하면서 풀면 될 것 같습니다. 문제해결 원숭이와 멍멍이는 운명의 라이벌입니다. 원숭이가 멍멍이 머리를 쓰담쓰담하고 싶은데 키가 작아서 매일 주문을 외웁니다. 주문 덕분에 원숭이는 하루에 키의 양을 1cm 늘릴 수 있습니다. 예를 들어 어제 4cm 컸으면 오늘은 3cm, 4cm, 5cm 중에 하나만큼 키를 늘릴 수 있습니다. 계속 키를 늘리면 좋겠지만 원숭이의 키는 시작 날과 끝 날에 무조건 1cm만 늘릴 수 있습니다. 예를 들어 8cm 커야한다면 아래와 같이 최소 5일이 걸리겠습니다. 1일 2일 3일 4일 5일 1cm 2cm 2cm 2cm 1cm 1일 2일 3일 4일 5일 6일 ..

문제소개 2302극장 좌석 문제의 응용 문제라고 생각됩니다. 극장 좌석을 좌우로 움직여보면 피보나치 수열이라는 것을 금방 알 수 있습니다. 2305자리배치 또한 피보나치라는 점을 생각해서 문제에 접근하였습니다. 문제해결 1 2 3 4 다음과 같이 4개의 좌석이 있으며 그 중에 2번은 자유석입니다. 자유석을 제외한 좌석은 지정석입니다. 지정석 표를 산 사람은 해당 지정석, 해당 지정석 좌우 그리고 자유석에 앉을 수 있습니다. 예를 들어 3번 지정석을 구매한 사람은 3,4번 그리고 2번에 앉을 수 있습니다. 이러한 조건을 만족하면서 배치할 수 있는 경우의 수를 구하는 문제 입니다. 2가지 풀이 방법을 생각해봤습니다. 1) 자유석에 앉는 경우 + 자유석에 앉지 않는 경우 2) 자유석을 기준으로 좌,우 구분하는..

그래프 분류 문제 날짜 난이도 소스 풀이 DFS 2931.가스관 2018.10.25 중 DIJKSTRA 10282.해킹 2018.10.26 중 보기 MCMF 3980.선발 명단 2018.10.27 중 보기 MCMF 11405.책구매하기 2018.10.29 중 보기 BFS 11559.Puyo Puyo 2018.10.30 하 보기 BFS 12761.돌다리 2018.11.07 하 보기 트리 1135.뉴스 전하기 2018.11.20 중 보기 크루스칼 6497.전력난 2018.12.02 하 보기 크루스칼 1774.우주신과의 교감 2018.12.02 하 보기 크루스칼 4386.별자리 만들기 2018.12.02 하 보기 DISJOINT SET 1976.여행 가자 2018.12.02 하 보기 BFS 2615.오목 20..