문제링크 : http://codeup.kr/problem.php?id=3704

해결 방법 :

n 이 5라면은 다음과 같이 총 13가지 경우의 수를 알 수 있다.

5=1+1+1+1+1

5=1+1+1+2

5=1+1+2+1

5=1+2+1+1

5=2+1+1+1

5=1+1+3

5=1+3+1

5=3+1+1

5=1+2+2

5=2+1+2

5=2+2+1

5=2+3

5=3+2

이걸 보고 생각해보면 5를 도달하기 직전 시점에서 보면 한 칸 전에오는 경우의수 가 있을 것이고, 두 칸 전에 오는 경우의 수도 있을거고 그리고 세 칸전에 오는 경우의 수가 있을것이다.

그렇다면 n에 도달하는데 모든 경우의 수는 n-1까지 오는데 경우의수 + n-2 까지 오는데 경우의 수 + n-3 까지 오는데 경우의수로 모든 경우를 다 합해주면은 원하는 답을 구할 수 있다.

이렇게하면 정답은 구할수 있지만, 이렇게 모든 경우를 세주면은 하나의 경우에있어서 계속 3가지의 경우의수가 발생이 되므로 3의 n승이라는 어마어마한 시간이 걸려서 틀리게 된다.

따라서, 중복되는 경우를 세주지 않게하기위해서 memo라는 배열에 n에 도달하는 경우의수를 미리 기록해둔다.

그렇게되면 일단 n이 1씩계속 감소하며 모든경우를 구하게 되고 n-2, n-3으로 부르는 재귀함수는 n-1의 재귀함수에 모두 포함되므로 경우의수가 확 줄어들게 된다. 

이제 코드를 작성해 보면 다음과 같다.

문제링크)

- http://codeup.kr/problem.php?id=3733

해결방법)

어떤 임의의 자연수 n 을 입력받고 홀수 or 짝수 일때의 각각의 규칙에 따라 재귀함수를 호출한다.

이때 재귀함수 호출 횟수가 몇번인지가 문제에서 말한 우박수의 길이가 되고 이것을 구하면 된다.

규칙은 다음과 같다.

1. 어떤 자연수 n이 입력되면,

2. n이 홀수이면 3n+1을 하고,

3. n이 짝수이면 n/2를 한다.

4. 이 n이 1이 될때까지 2~3과정을 반복한다.

예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.

여기서 생각해야할 부분이 있는데, 입력이 자연수 a, b 구간으로  1<= a <= b <= 10,000,000 의 아주 큰 범위를 갖는다.

그래서 이 문제가 large 버전으로 이름이 붙여진 것 같다.

이 큰 값의 범위 입력을 풀기 위해서 대표적인 방법으로 메모이제이션을 써서 시간복잡도를 줄여야 겠다는 생각을 했다.

그리고 코딩하면서 알게 된것이 배열을 천만으로 선언할 수 있다는 것을 알 수 있었다. 너무 비효율적이라 생각되는데 무튼 문제만 푼다면야...하고 일단 넘어가자.

메모이제이션을 할때 천만으로만 하기 때문에 n이 홀수여서 천만의 값을 넘어간다면 이는 따로 조건을 추가해서 메모이제이션을 안하고 다음 재귀함수를 그냥 호출 하는 방식으로 구해보았다.

문제링크) http://codeup.kr/problem.php?id=2606

해결방법)

분자와 분모가 주어지는데 실제 나누기를 해보면 소수점 이하부분만 출력하기위한 규칙이 보여진다.

처음에는 단순하게 생각할수있는 것이 실제 나눠봐서 정수부분을 빼고 *100억을해서 출력해서 정답이었지만,

모범답안은 그렇지 않았다.

항상 분자를 분모로 나눈 나머지 *10 에서 분모를 나눈 몫이 소수점 이하 부분의 값이었다.

이를 10번만 반복하면 소수점 이하 10번쨰자리까지 구할 수 있게 된다.

소스코드)

캔디팡 문제 링크 : http://codeup.kr/JudgeOnline/problem.php?id=2605

해결 전략)

2차원 맵정보가 있는데 각 좌표마다 방문하면서 4방향(상,하,좌,우)에 인접해있는 모든 개수정보를 알고 결국, 인접해있는개수가 3개이상이면 카운팅을 해줘서 답을 구할수있다.

예를 들어서 그린 그림입니다.

여기서 인접해 있는 것이 보인다면 그 곳으로 좌표이동하고 다시 4방향으로 인접해 있는 개수정보를 파악한다.

이 작업을 모든 맵 좌표를 방문하면서 체크하게 된다. 단, 방문이 된 곳은 체크를 따로해줘서 재탐색이 이뤄지지 않도록 한다.

소스코드)