free from

문제소개 5721 사탕 줍기 대회 복잡한 부분을 어떻게 하면 간단하게 정리할 수 있을까를 생각하는게 중요한 것 같습니다. 아래 그림과 같이 3 X 3 칸에서 11개의 사탕을 줍는다면 윗 줄,아랫 줄, 좌, 우의 사탕은 먹지 못합니다. 못 먹는 사탕을 0으로 바꾸는 작업을 하게 된다면.. 문제는 미궁 속으로 빠집니다. 이러한 복잡한 부분을 어떻게 간단하게 바꿀 수 있을까요? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 문제풀이 1 8 2 1 9 1 7 3 5 2 1 2 10 3 10 8 4 7 9 1 7 1 3 1 6 다음과 같은 그림이 있습니다. 3 X 3 칸에서 10개의 사탕을 줍는다면 윗 줄, 아랫 줄은 못 먹습니다. 그러나 3 X 3이 속한 3행의 1, 10은 먹을 수 있습..

문제소개 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..