문제는 더블릿 10 divide and conquer에 있는 mod_fibo입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/mod_fibo/mod_fibo.php?pname=mod_fibo 엄청 큰 피보나치 수를 구하는게 문제입니다.피보나치 수열의 단순한 방법(전전값과 전값의 합)으로는 시간초과가 뜹니다. 나눗셈을 미리 해주는 방법도 마찬가지로 시간초과가 납니다.풀기 위해서는 행렬을 이용해주는 방법이 있습니다.1 11 0을 피보나치 수열의 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...에서 첫번째 1에 해당하는 행렬로보고 값은 0행 0열의 값을 봅니다.이 행렬을 제곱하면 2 11 1이 나오고 이 값은 2에 대항하는 행렬입니다.이 행렬을 제곱하면5..

문제는 더블릿 25 backtracking에 있는 door입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/door/door.php?pname=door 열린 문 2곳이 있고 앞으로 열어야 하는 문을 열린 문으로 이동하면서 이동한 거리를 카운트합니다. 이 때 이동한 거리가 가장 적은 회수를 구하는 문제입니다.다음에 열어야 할 문은 열린 문 2군데중 한 군데와 바꿀 수 있습니다.무조건 가까운 거리와 바꿨다가는 다음 경우의 수에서 더 많은 거리를 이동해야 할 수 있습니다.이번에 열어야 할 문을 열린 문 2곳 중에 왼쪽문과 바꾼 경우, 오른쪽문과 바꾼 경우를 모두 트리를 타듯이 타고 내려갑니다.열린 문이 2와 5이고열어야 할 문이 3 4 6 5 인 경우첫 번째 문 교체 (2-..

문제는 더블릿 25 backtracking에 있는 scales입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/scales/scales.php?pname=scales 입력받은 무게들의 합이 반이 되는 부분집합의 수를 구하는 문제입니다.이를 구하기 위해선 예제인 1 9 5 3 8로 볼 경우11 91 9 51 9 5 3 81 51 5 3등 모든 경우의 수를 봐야합니다.이럴 때 백트래킹을 쓰는데 재귀를 사용합니다.우선 1 9 5 3 8을 배열에 입력 받고 재귀를 호출하는 방식은 다음과 같습니다.현재 값으로 그냥 호출, 현재값에 다음값을 더해 호출두 경우 모두 각각 카운터값을 1씩 증가시킵니다.그럼 첫 번째 값 1에 대해 다음 호출은 1과 1+9가 됩니다.그 다음 호출은 1에..

문제는 더블릿 14 queue에 있는 catch_cow입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/catch_cow/catch_cow.php?pname=catch_cow 수 N과 K가 주어지고 N을 *2, +1, -1을 한번 할 때마다 카운터가 증가합니다. 이 때 N이 K가 될 수 있는 가장 적은 경로(카운터 크기)를 구하면 됩니다.친절하게 queue로 풀으라고 알려주고 있으니 그렇게 만듭니다. 기본적으로 리스트에 어떤 경우의 값을 다 넣어주고 반복이 진행되면서 그 값들을 전부 빼서 검사를 진행합니다. 그리고 그 결과 답이 나오지 않으면 다음 경우의 수들을 다시 리스트에 전부 넣어주고 검사하는 것을 반복합니다.먼저 첫 N값을 리스트에 넣습니다.그리고 bfs를 실행..

문제는 더블릿 2 if에 있는 cross입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/cross/cross.php?pname=cross 두 줄이 교차하는지 아닌지를 검사하는 문제입니다.두 선이 교차하는 경우는 받아 들인 선의 각 끝점을 a1(큰 수), a2(작은 수)와 b1(큰 수), b2(작은 수)라고 했을 때,a1이 b1과 b2사이에 있고 a2가 b2보다 작을 때와 그 반대의 경우가 있습니다.

문제는 더블릿 옥상에 있는 koi_vote입니다.문제 사이트 주소입니다.http://183.106.113.109/pool/koi_vote/koi_vote.php?pname=koi_vote 각 후보에게 투표한 점수가 가장 높으면서 높은 점수의 표를 가장 많이 받은 후보와 그 점수를 출력하면 되는 문제입니다.그냥 각 후보에 대해 점수를 합할 수 있는 변수와 1점, 2점, 3점 득표수를 저장할 수 있는 변수를 만들고 입력받을 때마다 각 변수에 알맞게 연산을 해준 다음에 if문을 이용해 결과를 출력해주면 됩니다.