멤고리즘 6회 3번, 증가-팬린드롬(DP)

알고리즘/멤고리즘 2014. 5. 10. 13:18

증가-팬린드롬


문제 

양의 정수의 수열이 주어질 때 앞으로 읽던 뒤로 읽던 같은 수열이면 “팰린드롬“이라고 한다.


예를 들어, 두 수열은 “팰린드롬” 이다.


23 11 15 1 37 37 1 15 11 23

1 1 2 3 4 7 7 10 7 7 4 3 2 1 1


“팰린드롬” 수열 중 중간 위치에 있는 수까지 감소하지 않는 수열은 “증가-팰린드롬”이라고 한다.


23 11 15 1 37 37 1 15 11 23   => “증가-팰린드롬”이 아니다.

1 1 2 3 4 7 7 10 7 7 4 3 2 1 1  => “증가-팰린드롬”이다.


양의 정수 N이 주어질 때 수열의 합이 N이 되는 “증가-팰린드롬”의 개수를 구하라. 


주어지는 입력의 경우의 수는 64 비트 정수로 표현이 가능하다.


몇가지 보기를 보면,


1: (1)

2: (2), (1 1)

3: (1 1 1)

4: (4), (1 2 1), (2 2), (1 1 1 1)

5: (5), (1 3 1), (1 1 1 1 1)

6: (6), (1 4 1), (2 2 2), (1 1 2 1 1), (3 3), (1 2 2 1), (1 1 1 1 1 1)

  

예제 입력​1

2

예제 출력1

2

예제 입력​2

8

예제 출력2

11

출제자 : 안일규


저작자표시

'알고리즘 > 멤고리즘' 카테고리의 다른 글

멤고리즘 6회 2번, 멤버십 복사기(if)  (0) 2014.05.10
멤고리즘 6회 1번, 쉼표(문자와 문자열)  (0) 2014.05.10
멤고리즘 5회 3번, 돈줍기(DP)  (0) 2014.05.10
멤고리즘 5회 2번, 2등신 영훈이(문자와 문자열)  (0) 2014.05.10
멤고리즘 5회 1번, 멤고리즘 랭킹(정렬)  (0) 2014.05.10
Posted by 밍쫑
,

멤고리즘 5회 3번, 돈줍기(DP)

알고리즘/멤고리즘 2014. 5. 10. 13:13

돈줍기


문제 

N 개의 돈이 놓여있다. 돈을 마음껏 주워갈 수 있다. 단, 연속해서 3개 이상의 돈을 줍지는 못한다.

가장 많은 돈을 줍는 프로그램을 만들어 보자.

 

입력

1<=N<=1000, 돈의 크기는 100 이하이다.


출력

가장 많이 주울 수 있는 돈의 액수를 출력하라.

 

예제 입력​

8
5 7 10 1 2 10 11 6

예제 출력

38


입출력 예

7 + 10 + 10 + 11 = 38

출제자 : 안일규


저작자표시

'알고리즘 > 멤고리즘' 카테고리의 다른 글

멤고리즘 6회 2번, 멤버십 복사기(if)  (0) 2014.05.10
멤고리즘 6회 1번, 쉼표(문자와 문자열)  (0) 2014.05.10
멤고리즘 5회 2번, 2등신 영훈이(문자와 문자열)  (0) 2014.05.10
멤고리즘 5회 1번, 멤고리즘 랭킹(정렬)  (0) 2014.05.10
멤고리즘 4회 3번. 운영자의 사탕 (DP)  (0) 2014.04.22
Posted by 밍쫑
,

멤고리즘 4회 3번. 운영자의 사탕 (DP)

알고리즘/멤고리즘 2014. 4. 22. 23:20

운영자의 사탕


문제

위 운영자님에게 N개의 사탕이 생겼다. 운영자님은 N개의 사탕을 K명의 회원들에게 나눠주고 싶어한다. 그런데 멤버십 회원들 사이에는 서열이 존재하여, 서열이 높은 사람은 서열이 낮은 사람보다 같거나 많은 수의 사탕을 받아야한다. 모든 멤버십 회원이 사탕을 1개 이상은 받아야 한다고 가정한다. 

사탕 수와 회원 수가 주어졌을 때, 사탕을 나눠주는 경우의 수를 구해보자.

 

입력

사탕 수 N ( 1 <= N <= 200 ), 회원 수 K ( 1 <= K <= N ) 가 입력으로 주어진다.

출력

결과는 64 비트 정수 형내의 값이다.

 

예제 입력​

7 3

예제 출력

4

입출력 설명

1 1 5
1 2 4
1 3 3
2 2 3

출제자 : 안일규



(http://183.106.113.109/30stair/moving/moving.php?pname=moving)

저작자표시

'알고리즘 > 멤고리즘' 카테고리의 다른 글

멤고리즘 5회 2번, 2등신 영훈이(문자와 문자열)  (0) 2014.05.10
멤고리즘 5회 1번, 멤고리즘 랭킹(정렬)  (0) 2014.05.10
멤고리즘 4회 2번. 규민이는 유성온천 부자 (재귀, BFS)  (0) 2014.04.22
멤고리즘 4회 1번. 먹보 영훈이2 (칼로리 계산)  (0) 2014.04.22
멤고리즘 3회 3번. 술잔 나누기  (0) 2014.04.22
Posted by 밍쫑
,

멤고리즘 2회 3번. 산삼 찾기(DP)

알고리즘/멤고리즘 2014. 4. 22. 23:11

유정이의 산삼


문제


N * N 크기의 숲이 있다. 이 숲에는 1000년 묵은 산삼이 군데군데 자라고 있어서 유정이는 익균이의 자동차를 타고 산삼을 먹으려 한다.

익균이의 자동차는 (1, 1)의 위치에서 출발하여 (N, N)까지 이동하는데, 익균이의 자동차는 고물이라 오른쪽 또는 아래쪽으로밖에 움직이지 못한다. 유정이는 무한한 양의 산삼을 먹을 수 있다고 가정(?)하자.

익균이의 자동차를 이용해 유정이가 최대한 많이 산삼을 먹도록 하는 프로그램을 작성하시오. 

입력

첫 줄에는 숲의 크기 N (3 <= N <= 100)이 주어진다.

둘째줄부터는 주어진 지도가 N줄 만큼 입력된다. (단, 0은 산삼 없음, 1은 산삼 있음을 의미한다.)


출력

유정이가 먹을 수 있는 최대 산삼의 양을 출력한다.

예제 입력

5
0 1 0 0 1
0 0 1 0 0
1 0 1 1 0
1 1 0 1 0
1 0 0 0 1

예제 출력

6


[문제 설명]

(이런 문제의 경우, 손으로 직접 예제를 풀어보면서 문제를 이해하시는 게 제일 도움이 됩니다.)

문제에서 오른쪽 또는 아래쪽으로만 움직일 수 있고, 움직이면서 최대한 많이 산삼을 먹는게 목표인데요.

즉, 오른쪽 또는 아래쪽으로 이동해보면서 1을 가장 많이 지나는 경우를 찾으시면 됩니다.


[소스코드 설명]

저같은 경우 배열을 (1, 1)부터 사용을 하기 위해서 배열 사이즈를 하나 더 늘려주고, 처음에{0, 0}으로 초기화를 하였습니다. 이렇게 하시면은 비교를 할 때 맵의 크기를 넘어가는 경우에 대해서도 예외처리를 안해도 되기 때문에 매우 편합니다.


제가 짠 코드를 디버깅 돌려보면 다음과 같은 결과가 나옵니다.

0 

1 

2 

3 

4 

5 

0 

0

0

0

0

0

0

 1

0

0

1

1

1

2

 2

0

 0

1 

2 

2 

 2

 3

 0

 1

1 

3 

4 

4 

 4

 0

 2

3 

3 

5 

5 

 5

 0

 3

3 

3 

5 

6 





저작자표시

'알고리즘 > 멤고리즘' 카테고리의 다른 글

멤고리즘 3회 2번. 색종이(피자) 쪼개기  (0) 2014.04.22
멤고리즘 3회 1번. 오목 (재귀)  (0) 2014.04.22
멤고리즘 2회 2번. 이진회귀수  (0) 2014.04.22
멤고리즘 2회 1번. 거꾸로 말해요  (0) 2014.04.22
멤고리즘 1회 3번. 복붙기능 키보드  (0) 2014.04.22
Posted by 밍쫑
,

티스토리툴바