[완료]알고리즘 어떻게 작성해야할까요??

mmx822의 이미지

질문 제목 : 이런 문제.. 알고리즘을 어떻게 짜야할까요??

질문 요약 : DP(다이나믹프로그래밍) 으로 이 문제를 해결해야하는데.. 어떻게 해야하는건지;;

질문 내용 : 아래의 문제를 어떻게 구현해야할까요??

문제는 너무 길구요.. 대략 어떻게 구현하라는 정보가 있길래 이거를 보여드릴테니 실제 C언어 상에선 어떻게 코딩을 해야하는건지 알려주세요.. ㅜ

EE[M,M,1] = EE[M,M,2] = 0

EE[i,i,1] = EE[i,i,2] = 무한대 if i != M

DD[i,i,1] = DD[i,i,2] = PP[i,i,1] = PP[i,i,2] = 0

D[1~N] 과 W[1~N] 그리고 N, M은 input으로 들어오기에 이미 값이 들어있음..

최종 목표 : min { EE[1,N,1], EE[1,N,2]}

EE[L,R,1] = min {EE[L+1,R,1] + (DD[L+1,R,1] + D[L+1] - D[L]) * W[L],

EE[L+1,R,2] + (DD[L+1,R,2] + D[R] - D[L]) * W[L]}

EE[L,R,2] = min {EE[L,R-1,1] + (DD[L,R-1,1] + D[R] - D[L]) * W[L],

EE[L,R-1,2] + (DD[L,R-12] + D[R] - D[R-1* W[L]}

DD[L,R,1] = (DD[L+1,R,1] + D[L+1] - D[L]) 만약 EE에서 min이 앞에 것일 경우적용

(DD[L+1,R,2 + D[R]- D[L]) 만약 EE에서 min이 뒤에 것일 경우 적용

DD[L,R,2]= (DD[L,R-1,1] + D[R] - D[L]) 만약 EE에서 min이 앞에 것일 경우적용
(DD[L,R-1,2] + D[R] - D[R-1]) 만약 EE에서 min이 뒤에 것일 경우적용

PP[L,R,1] = L+1 만약 EE에서 min이 앞에 것일 경우적용
R 만약 EE에서 min이 뒤에 것일 경우적용

PP[L,R,2] = L 만약 EE에서 min이 앞에 것일 경우적용
R-1 만약 EE에서 min이 뒤에 것일 경우적용

위와 같은데요..위에서 배열의 제일 끝에 달린 1과 2는 아마.. 배열을 따로 EE1 EE2 이런식으로 나눠야하는거 같네요..
문제는.. 위와 같은 힌트를 가지고 구현을 해야하는데.. 어떤 형식으로 짜야 DP 알고리즘으로
최종목표인 min { EE[1,N,1], EE[1,N,2]} 를 구할 수 있을까요?? 제가 이거 지금 계속 붙잡고 있는데도 도저히 모르겠거든요 ㅜ
코딩을 짜달라는건 아니구요.. 대충 어떻게 구현을 해야하는지 방향만 잡아주시면 감사하겠습니다 (__)

jachin의 이미지

EE 는 MxM 크기의 2차원 배열이 2 개 있는 공간이라고 가정하고, 가장 오른쪽 아래 끝에 0, 사선으로 무한대의 값을 갖는 행렬인가보군요.
DD 와 PP 는 EE와 마찬가지로 2차원 배열이지만, 사선으로 0을 갖는 행렬이고요.
D, W, N, M 은 이미 주어진 1차원 배열이고요.

먼저 EE 에 대한 배열을 정의해야 하지 않을까요? M 을 100 이라고 가정하고 EE 를 선언해보죠. (아마 Maximum 을 나타낸 것이라 생각되네요.) 대신, 배열의 자료 형식을 정수로 선언하고, 무한대를 정수 자료형 최대 값(INT_MAX)으로 가정하지요. limits.h 파일을 포함하는 것을 잊지 말아주세요.

int EE[100,100,2];
int i;
for ( i = 0 ; i < 99 ; i++ ) EE[i,i,1] = INT_MAX;
for ( i = 0 ; i < 99 ; i++ ) EE[i,i,2] = INT_MAX;
EE [99, 99, 1] = 0; EE [99, 99, 2] = 0;

이런 식으로 각각의 전제식에 비어있는 배열값을 채워가며, 결과값을 얻으면 되리라 생각합니다.

알고리즘을 짜야 하는 것이 아니라, 다이나믹 프로그래밍 방식으로 각각의 식을 하나의 작은 문제로 보고, 하나씩 함수를 정의하여 문제해결을 하라는 의미 아닐까요?

익명 사용자의 이미지

답글 달면서 지낸지 10년이 다 되어간다면서...

어떻게 기초적인 배열 문법도 모르지...

같은 루프를 2번씩 돌리는것도 개코메디고...

limits.h 파일을 포함하는 것을 잊지 말라니 대체 누가 누구한테 충고질이지...

머릿속에 개념을 포함하는 것을 잊지 말아주세요...

라고 충고하고 싶다 레알...

그리고 말야...

내가 하루에 몇번 접속을 하는지 마는지 하루종일 체크하고 있냐...

일이 많아서 정신이 없다면서 겨우 한다는짓이 img.kde.kr에다 이미지 올려놓고 남 뒷조사질이냐...

그딴시간에 C언어 교본이라도 한줄을 더 보라고 젭라...

10년동안 그딴 뻘짓을 해놓으니까 아직도 배열을 어떻게 선언하는지 모르자나...

쌩기초같은 배열 선언도 제대로 못하면서 멀티 스레드가 어쩌구 리눅스커널이 어쩌구 아놔...

그리고 분명히 질문한 사람이 코딩을 짜달란건 아니라고 했지...

아는것만 적으라고 젭라...

왜 개코메디같은 코딩을 짜서 개망신을 당하는거지...

개코메디는 답이 없다 레알...

snowall의 이미지

그럼 틀린 부분을 어떻게 고쳐야 하나요?

피할 수 있을때 즐겨라! http://melotopia.net/b

xgate의 이미지

특정 인물의 글에 기분나쁜 댓글을 다는 병적인 집요함이 있군요.혹시 그 과정을 즐기는건지..

여기가 "교과서"도 아니고 "프로그래밍의 정석"도 아닌데 왜 정확한 답변만 달려야 하나요?

틀렸다고 생각하는 부분이 있다면 직접 "이 부분은 잘못 되었습니다." 하고 댓글을 다시면 되잖아요. :)

질문자 삼천포로 빠지라고 일부러 그러는 것도 아닌데.

그렇게 잘 아시면 답변을 잘 쓰셔서 질문자에게 도움을 주시지요.

(아, 물론 도움이 될만한 지식이 있으시다면요.)

익명 사용자의 이미지

윗분하고는 다른 익명인데요
이제보니 jachin님은 자기 프로필 이미지에 억세스하는 사람들
다 로그파일로 남겨 추적하시는가 보네요?
솔직히 좀 기분나쁘네요
kldp사람들 아이피랑 액세스 시간 다 기록해서 대체 뭐에 쓰실라고...
지금껏 활동 열심히 하신 것도 어떻게든 더 많은 글에 이미지를 끼워넣어
아이피수집에 용이하게 하기 위함이 아닌가 의심이 될 정도입니다
아닌게아니라 답변의 질이 떨어지는것도 적지않고...

이런 사람이 한둘이 아닐텐데 프로필에 이미지 링크거는거 금지시켜야 하지 않나요?

neocoin의 이미지

저 위에 프로필 이미지는 kldp 에 업로드 되어서 추적이 불가능합니다.
변경된거라면 모르겠는데, 이런 이야기를 하시려면 좀 더 합리적인 근거를 말씀해 주시면 좋겠네요.

neocoin의 이미지

변경하신거네요. 다른 글을 통해서 알았습니다.
이건 다른 분들이 불쾌할수 밖에 없는 건이군요.

익명 사용자의 이미지

제가 설명이 좀 부족했던 것 같군요.

단순 프로필 사진이 아니라 시그니처에 있었던, 지금은 jachin님께서 삭제한, 이름과 KDE에서의 역할이 적혀있던
가로로 길쭉한 이미지 파일을 얘기하는 것입니다.

KLDP에서는 시그니처라 해서 자기 글 밑에 자동으로 서명이 들어갈 수 있는데,
여기에 태그를 이용해 외부 사이트의 이미지를 삽입할 수 있습니다.

근데 브라우저가 이 이미지를 읽어 표시할 때마다 읽는 사람의 IP랑 리퍼러가 이미지가 있는 사이트로 전송이 되겠죠?
jachin님은 이걸 악용해서 자기 글을 보는 사람들이 어느 페이지에서 왔고 또 무슨 IP인지를 로그파일로 남긴 겁니다.

또한, 이건 자기 글에 대해 답글을 다는 사람을 확인할 때 특히 유용합니다.
답글 다는 페이지가 http://kldp.org/comment/reply/123/456 이런 식으로 되기 때문에...
물론 답변을 달려다가 지운 사람일 수도 있지만
몇번 반복되면 자기한테 달라붙는 스토커는 누구인지 알수가 있지요.

자기한테 악플 다는 악플러가 누구인지 확인하고픈 마음은 이해가 가지만
이건 광역 추적이라서, jachin님이 글을 올리신 쓰레드마다 모든 회원의 IP랑 액세스 시간, 리퍼러가 추적이 됩니다.
그밖에 브라우저에서 전송되는 여러 유익한 정보들도 덤으로 수집이 되겠죠?

게다가 이건 익명 상대로만 되는게 아니고, neocoin님 같이 회원님들의 정보도 무차별적으로 수집해 가는 겁니다.
위치에 따라서는 IP정보만이라도 위치추적이나 때로는 직장과 직위까지도 알 수가 있지요.

무슨 KLDP 관리자도 아니고, 이렇게 사용자들 정보를 무차별적으로 긁어가는데 기분이 좋을까요.

악플을 안달면 상관 없지 않느냐 라고 생각하실지 모르나,
악플이야 원래 KLDP에 로그가 남느니만큼 굳이 저런 짓을 안해도 고소 걸면 바로 잡히는거고,
jachin님이 사실 자기한테 악플 다는 사람 물먹이고 싶으면 그냥 경찰서 가면 끝나는 일이었는데,
굳이 저런식으로 상당기간 동안 KLDP 사람들 정보를 긁어가실 필요성이 뭐였을까요.

분명 IRC 같은 데서 낄낄대며 까댔을거고, 거기엔 님 얘기도 있을지도 모르겠군요.

neocoin의 이미지

저는 관련 기술을 이해하고 있으며, 저를 지칭해서 공감을 얻으실 노력을 하실 필요 없습니다.
악플에 대한 입장은 십분 이해하나 과하다는 것에 동의하며, 해당 논의는 이 쓰레드가 아니라 해당 다른 쓰레드에서 이루어 져야 한다고 생각합니다.

emptynote의 이미지

도대체 브라우저상 전송되는 정보랑 IP, 접근시간, 그리고 리퍼러(?)에 개인정보가 있나요?

도대체 그 유익한 정보가 도대체 무엇인가요?

그렇게 수집된 정보로 1원이라도 상업적인 가치로 활용할 수 있는 정보가 있다면 말씀해주실수있나요.

만약 1원이라도 상업적인 가치가 있다면

모든 웹서버 운영하는 업체들한테 그만큼의 돈을 받아야 하지 않나요?

요새 돈도 궁하니 잃어버린 권리를 찾고자 하니

변호사 찾아갈 수 있게 아주 구체적으로 말씀해주셨으면합니다.

익명 사용자의 이미지

addnull의 이미지

질문자께서 작성한 수식에 오타(라고 믿어지는 부분)를 고치고 보기 좋게 정렬해보았습니다.

EE[M,M,1] = EE[M,M,2] = 0
 
EE[i,i,1] = EE[i,i,2] = 무한대 if i != M
 
DD[i,i,1] = DD[i,i,2] = PP[i,i,1] = PP[i,i,2] = 0
 
D[1~N] 과 W[1~N] 그리고 N, M은 input으로 들어오기에 이미 값이 들어있음..
 
최종 목표 : min { EE[1,N,1], EE[1,N,2] }
 
EE[L,R,1] = min {
    EE[L+1,R,1] + (DD[L+1,R,1] + D[L+1] - D[L])   * W[L],
    EE[L+1,R,2] + (DD[L+1,R,2] + D[R]   - D[L])   * W[L]
}
 
EE[L,R,2] = min {
    EE[L,R-1,1] + (DD[L,R-1,1] + D[R]   - D[L])   * W[L],
    EE[L,R-1,2] + (DD[L,R-1,2] + D[R]   - D[R-1]) * W[L]
}
 
DD[L,R,1] =
    (DD[L+1,R,1] + D[L+1] - D[L])    만약 EE에서 min이 앞에 것일 경우 적용
    (DD[L+1,R,2] + D[R]   - D[L])    만약 EE에서 min이 뒤에 것일 경우 적용
 
DD[L,R,2]=
    (DD[L,R-1,1] + D[R]   - D[L])    만약 EE에서 min이 앞에 것일 경우 적용
    (DD[L,R-1,2] + D[R]   - D[R-1])  만약 EE에서 min이 뒤에 것일 경우 적용
 
PP[L,R,1] =
    L+1    만약 EE에서 min이 앞에 것일 경우 적용
    R      만약 EE에서 min이 뒤에 것일 경우 적용
 
PP[L,R,2] =
    L      만약 EE에서 min이 앞에 것일 경우 적용
    R-1    만약 EE에서 min이 뒤에 것일 경우 적용

이미 EE에 관한 점화식이 주어진 상황이라서 식을 그대로 구현하면 될 거라 생각했는데요.
아래 초기값이 문제가 되는군요.

EE[M,M,1] = EE[M,M,2] = 0
 
EE[i,i,1] = EE[i,i,2] = 무한대 if i != M

만약 EE[1,2,1] 값을 구한다고 보면, EE[2,2,1] 과 EE[2,2,2]의 값을 참조해야 하는데 둘 다 infinite number 이므로
엄밀하게 수학적인 정의로 따지면 두 infinite number 크기 비교가 불가능하기 때문에
뒤에 있는 DD[1,2,1], PP[1,2,1]의 값을 구할 수 없습니다.

EE[1,2,1] = min {
    EE[2,2,1] + (DD[2,2,1] + D[2] - D[1]) * W[1],
    EE[2,2,2] + (DD[2,2,2] + D[2] - D[1]) * W[1]
}
 
DD[1,2,1] =
    (DD[2,2,1] + D[2] - D[1])    만약 EE에서 min이 앞에 것일 경우 적용
    (DD[2,2,2] + D[2] - D[1])    만약 EE에서 min이 뒤에 것일 경우 적용
 
PP[1,2,1] =
    2    만약 EE에서 min이 앞에 것일 경우 적용
    2    만약 EE에서 min이 뒤에 것일 경우 적용

이 경우에는 DD[1,2,1] 과 PP[1,2,1] 의 분기에 따른 대입(assign) 값들이 동일하기 때문에
EE[1,2,1] = min { inf, inf }
식의 결과와 상관없이 결과적으로
DD[1,2,1] = D[2] - D[1]
PP[1,2,3] = 2
라고 됩니다만, 이것이 전체 점화식에서 min{ inf, inf } 일 때마다 동일하게 보이는 현상인지는 확신이 안 가네요.

언릉 제 머리에 떠오르는 생각은
EE[1,2,1], EE[1,2,2] 둘 다 inf 가 되고 이 값으로 EE[1,3,2] 값이 구해지고 .. 이런 식으로 계속 식을 풀다보면
DD와 PP 의 분기에 따른 대입 값이 다른데 EE를 구할 때 min{ inf, inf } 해야 하는 경우가 생길지도....모르겠습니다.?!?!

우선은 초기값 세팅이 정말로 맞는지 질문자께서 확인해주시길 바랍니다.

addnull의 이미지

음.. 역시 초기값이 문제인 것 같네요.
DD랑 PP 갱신은 생략하고 EE 점화식만 구현했습니다.

#include <stdio.h>
#include <limits.h>
 
#define INF		INT_MAX
#define M		20
#define N		5
 
int min(int arg0, int arg1);
int EE(int L, int R, int n);
int printTab();
 
int mEEFlag[M][M][3];
int mEE[M][M][3];
int mTabCount;
 
int main(int argc, char** argv) {
	int result =0;
	int result_left = 0;
	int result_right = 0;
 
	result_left = EE(1, N, 1);
	result_right = EE(1, N, 2);
	result = min(result_left, result_right);
	printf("final result = %d\n", result);
 
	return 0;
}
 
int EE(int L, int R, int n) {
	int result_left = 0;
	int result_right = 0;
 
	printTab();
	printf("start : EE(%d,%d,%d)\n", L, R, n);
 
	if (L == R && R == M) { 
		printTab();
		printf("end   : %d\n", 0);
		return 0;
	}
	if (L == R) {
		printTab();
		printf("end   : %d\n", INF);
		return INF;
	}
	if (mEEFlag[L][R][n] == 1) {
		printTab();
		printf("end   : %d\n", mEE[L][R][n]);
		return mEE[L][R][n];
	}
 
	if (n == 1) {
		++mTabCount;
		result_left = EE(L+1, R, 1);
		result_right = EE(L+1, R, 2);
 
		if (result_left == result_right && result_right == INF) {
			if (L+1 != R) {
				printTab();
				printf("error : EE(%d,%d,%d)\n", L, R, n);
				exit(0);
			}
 
			mEE[L][R][n] = INF;
		} else {
			mEE[L][R][n] = min(result_left, result_right);
		}
	} else if (n == 2) {
		++mTabCount;
		result_left = EE(L, R-1, 1);
		result_right = EE(L, R-1, 2);
 
		if (result_left == result_right && result_right == INF) {
			if (L != R-1) {
				printTab();
				printf("error !!!\n");
				exit(0);
			}
 
			mEE[L][R][n] = INF;
		} else {
			mEE[L][R][n] = min(result_left, result_right);
		}
	}
 
	mEEFlag[L][R][n] = 1;
 
	--mTabCount;
	printTab();
	printf("end   : %d\n", mEE[L][R][n]);
 
	return mEE[L][R][n];
}
 
int printTab() {
	int i = 0;
 
	for (i=0; i<mTabCount; ++i) {
		printf("    ");
	}
}
 
int min(int arg0, int arg1) {
	int ret = 0;
 
	ret = (arg0 < arg1) ? arg0 : arg1;
 
	return ret;
}

결과는 다음과 같습니다.

start : EE(1,5,1)
    start : EE(2,5,1)
        start : EE(3,5,1)
            start : EE(4,5,1)
                start : EE(5,5,1)
                end   : 2147483647
                start : EE(5,5,2)
                end   : 2147483647
            end   : 2147483647
            start : EE(4,5,2)
                start : EE(4,4,1)
                end   : 2147483647
                start : EE(4,4,2)
                end   : 2147483647
            end   : 2147483647
            error : EE(3,5,1)

이전 포스트에서 제가 말씀드렸던 것처럼
EE(3,5,1) 을 구하기 위해서 EE(4,5,1) 와 EE(4,5,2)를 참조하는데 이들의 값이 INF 입니다.
그러면

EE[3,5,1] = min {
    EE[4,5,1] + (DD[4,5,1] + D[4] - D[3]) * W[3],
    EE[4,5,2] + (DD[4,5,2] + D[5] - D[3]) * W[3]
}
 
DD[3,5,1] =
    (DD[4,5,1] + D[4] - D[3])    만약 EE에서 min이 앞에 것일 경우 적용
    (DD[4,5,2] + D[5] - D[3])    만약 EE에서 min이 뒤에 것일 경우 적용
 
PP[3,5,1] =
    4    만약 EE에서 min이 앞에 것일 경우 적용
    5    만약 EE에서 min이 뒤에 것일 경우 적용

이렇게 DD와 PP를 갱신할 때 EE의 결과에 대응하는 분기 별로 다른 값을 넣어야 합니다.
하지만 EE에서는 min{ INF, INF } 의 수식을 실행하므로 어느 쪽의 값을 넣어야 하는지 결정할 수 없죠.
혹시 제가 문제를 잘못 이해하고 있다면 알려주세요 :)

참고로 제 코드에서 mEEFlag 변수가 이전에 계산된 EE를 다시 계산하지 않고
이전의 결과값을 반환하게 하는 DP(dynamic programming)의 특징을 보여줍니다.

mmx822의 이미지

흠.. 이 문제는 정보올림피아드 기출문제입니다..
제가 문제의 전반적인걸 말씀드리지 않았더니...오해가 생긴 것 같네요 ㅎㅎ;;
문제입니다..
마을의 중심에는 매우 긴 도로가 있다. 이도로 변에는 가로등이 있다. 이 가로등을 모두 끄되 전력소비를 최소로하고 꺼야한다. 가로등을 끄는 일을 하는 사람은 정확히 1m/초의 속도로 움직이고,
가로등을 끈 동안의 시간은 무시한다.
입력의 첫 줄에는 2개의 정수 N과 M이 있다. 첫번째 정수 N(1<=N<=1000)은 가로등의 개수를 나타내는 정수이고, 두번째 정수 M(0<=M<=N) 은 가로등끄는 사람이 위치하는 가로등의 번호이다.
다음 N개의 줄에는 각 가로등에 관한 두개의 정수가 입력된다. 첫번째 정수 D(1<=D<=1000는 가로등의 위치를 나타내고, 두번째 정수는 이 가로등의 전력소비량 W(1<=W<=1000)을 나타낸다. 가로등의 위치는
마을이 시작되는 부분부터의 거리를 나타내며, 전력소비량은 1초당 소비되는 전력량을 나타낸다. 그러므로, 어떤 가로등의 전력소비량이 w이고, 이 가로등이 s초동안 켜져있는 동안에 소비된 전력량은 ws가 된다.
가로등의 위치를 나타내는 정수 D의 오름차순으로 입력된다. 같은 줄에 나타나는 정수들 사이에는 하나의 space가 있다. 가로등 번호는 입력되는 순서대로 1번, 2번 , ......, N번을 부여한다.

입력파일의 예
6
5
3 2
11 10
12 18
13 19
15 15
17 19

출력파일의 예
370
5
4
3
2
6
1

위에 설명한 것이 실제 문제이구요.. 제가 제일 위에 써놓은건 교수님께서 힌트를 주신 자료구조입니다..

mmx822의 이미지

EE[L,R,1]은 초기상태에서 L~R까지 다 끄고 현재 L에 있을 때까지의 총소비전력을 나타냅니다..
EE[L,R,2]은 초기상태에서 L~R까지 다 끄고 현재 R에 있을 때까지의 총소비전력을 나타냅니다..
DD[L,R,1]은 초기상태에서 L~R까지 다 끄고 현재 L에 있을 때까지의 총이동거리를 나타냅니다..
DD[L,R,2]은 초기상태에서 L~R까지 다 끄고 현재 R에 있을 때까지의 총이동거리를 나타냅니다..
PP[L,R,1]는 초기상태에서 L~R까지 다 끄고 현재 L에 있을 때까지의 바로 이전위치를 나타냅니다..
PP[L,R,2]는 초기상태에서 L~R까지 다 끄고 현재 R에 있을 때까지의 바로 이전위치를 나타냅니다..

M은 위 답글에서도 말씀드렸듯이 가로등끄는일을 하는 사람이 처음 서있는 가로등의 번호입니다..
따라서..
EE[M,M,1] = EE[M,M,2] = 0
EE[i,i,1] = EE[i,i,2] = 무한대 if i!=M
DD[i,i,1] = DD[i,i,2] = PP[i,i,1] = PP[i,i,2] = 0

최종목표 : min { EE[1,N,1], EE[1,N,2] } 가 되는 것입니다..
물론.. 최소 전력소비량이 되도록 거치는 가로등의 번호순서도 출력해야하겠죠??

mmx822의 이미지

EE[M,M,1]과 EE[M,M,2]와 EE[i,i,1] EE[i,i,2] 에서..
EE[M,M,1]과 EE[M,M,2]가 0이 되는 이유는 M은 처음 가로등끄는 사람이 서있는 위치이기때문에.. 전력소비 0인상태로 끌 수 있기 때문에 0인 것이고..
i = M 일 때를 제외한 EE[i,i,1]과 EE[i,i,2]가 무한대값인 이유는 절대 i위치에서 i위치로 갈 일은 발생하지 않기 때문에 무한대로 놓게 되는 것입니다..

addnull의 이미지

네, 문제를 이제 이해했습니다.

DP의 점화식 접근 방법을 제가 잘못 유추했군요.
초기 값은 질문자께서 올리신대로 세팅하는게 맞구요.
점화식을 푸는 시작을 min{ EE(1,N,1), EE(1,N,2) } 으로 해야하는게 아니라
EE(M, M, 1)과 EE(M, M, 2)로부터 시작해야 합니다.
아래 질문자께서 올리신 예제를 가지고 설명드리자면,

/* 입력파일의 예 */
6
5
3 2
11 10
12 18
13 19
15 15
17 19

과정이 recursive 하므로 반복 횟수별로 [1][2][3]... 숫자를 붙이겠습니다.

[1]
처음에는 (5, 5)에 대한 값을 알고 있으므로 이것으로부터
EE(4, 5, 1)
EE(4, 5, 2)
EE(5, 6, 1)
EE(5, 6, 2)
의 값을 얻을 수 있습니다.

예를 들면 EE(4, 5, 1) = min{ EE(5, 5, 1), EE(5, 5, 2) } 니까요.
여기서 EE(4, 5, 2) = min{ EE(4, 4, 1), EE(4, 4, 2) } 의 경우엔 초기값의 의해서 INF 가 됩니다.
사실 EE(4, 5, 2)는 직접 그림을 그려보시면 말도 안 되는 케이스임을 알 수 있습니다.
처음 시작 위치 5에서 시작해서 네번째와 다섯번째 전등을 끄고 다시 5의 위치로 온다는 건
반드시 최적해에 아무런 영향을 미치지 않는 나쁜 전략임을 알 수 있습니다.
앞으로 EE를 계산할 때 이런 경우들은 INF로 체크하시면 됩니다.

결론적으로 계산해보시면,
EE(4, 5, 1)
EE(5, 6, 2)
만 의미있는 값을 가지는걸 알 수 있습니다.

이제 (4, 5)와 (5, 6)에 대한 값을 알고 있습니다.
이것을 새로 추가한 "갱신된값"이라고 하겠습니다.
바로 이전에 알고 있던 (5, 5)는 더 이상 필요가 없습니다.
"갱신된값"이 있으면 그 값으로 또 갱신되는 값을 찾으면 되고, "갱신된값"이 없으면 반복은 종료됩니다.

[2]
"갱신된값"에서 (4, 5)로 부터는
EE(3, 5, 1)
EE(3, 5, 2)
EE(4, 6, 1)
EE(4, 6, 2)
을 구할 수 있구요.
(5, 6)으로 부터는
EE(4, 6, 1)
EE(4, 6, 2)
EE(5, 7, 1)
EE(5, 7, 2)
을 구해야하는데 마지막 두 개는 전등의 개수 N을 넘어가니까 무시됩니다.
즉 여기선
EE(3, 5, 1)
EE(3, 5, 2)
EE(4, 6, 1)
EE(4, 6, 2)
값이 구해지고 특히
EE(4, 6, 1)
EE(4, 6, 2)
위의 두 가지는 (4, 5)에서 왔을 때랑 (5, 6)으로 부터 왔을 때 중에 더 좋은 경우를 선택합니다.
PP 자료구조가 이런 경우에 어느 쪽을 선택했는지 기억하기 위한 거죠.

[3]
이제 "갱신된값"은 (3, 5), (4, 6) 입니다.
이것으로부터는
EE(2, 5, 1)
EE(2, 5, 2)
EE(3, 6, 1)
EE(3, 6, 2)
을 구할 수 있습니다.

[4]
"갱신된값"은 (2, 5), (3, 6) 입니다.
이것으로부터는
EE(1, 5, 1)
EE(1, 5, 2)
EE(2, 6, 1)
EE(2, 6, 2)
을 구할 수 있습니다.

[5]
"갱신된값"은 (1, 5), (2, 6) 입니다.
이것으로부터는
EE(1, 6, 1)
EE(1, 6, 2)
을 구할 수 있습니다.

[6]
"갱신된값"은 (1, 6)인데 더 이상 갱신할 수 없습니다.
반복을 종료합니다.

여기서 예시 입력 자료로 이뤄지는 모든 반복 단계는 끝났습니다.
경로를 출력하는 방법이 조금 복잡할 수 있는데요.
조금 생각해보시면 찾으실 수 있을 것 같습니다.

아래 제가 짠 코드가 있습니다.
직접 해결해보시다가 막히실 때 참고하시거나 질문자님의 솔루션과 비교해보시길 바랍니다.
저도 예제를 여러 개 돌려본게 아니라서 어딘가 헛점이 있을 거라 생각되네요. (윽.. ACM-ICPC의 악몽이...)

제가 미쳐 고려하지 못한 헛점은 너그러운 마음으로 답글로 남겨주세요 :)

#include <stdio.h>
#include <limits.h>
 
#define INF		INT_MAX
#define MAX		2000
 
void EE(int L, int R, int n);
void recursive();
void path(int L, int R, int last);
 
int N;
int M;
int D[MAX];
int W[MAX];
 
int mQueue[MAX*MAX][2];		// previous performed "EE(L, R, 0 or 1)"
int mQueueStart;
int mQueueEnd;
 
int mEE[MAX][MAX][3];
int mDD[MAX][MAX][3];
int mPP[MAX][MAX][3];
 
int main(int argc, char** argv) {
	int resultL = 0;
	int resultR = 0;
	int result_final = 0;
	int L = 0;
	int R = 0;
	int last = 0; // last position
	int i = 0, j = 0;
 
	// input
	scanf("%d", &N);
	scanf("%d", &M);
 
	for (i=0; i<N; ++i) {
		scanf("%d %d", &D[i+1], &W[i+1]);
	}
 
	// initialize
	for (i=0; i<MAX; ++i) {
		for (j=0; j<MAX; ++j) {
			mEE[i][j][1] = INF;
			mEE[i][j][2] = INF;
		}
	}
 
	mEE[M][M][1] = 0;
	mEE[M][M][2] = 0;
 
	mQueue[0][0] = M;
	mQueue[0][1] = M;
 
	mQueueStart = 0;
	mQueueEnd = 1;
 
	// do DP (dynamic programming)
	recursive();
 
	// min { EE[1,N,1], EE[1,N,2] }
	resultL = mEE[1][N][1];
	resultR = mEE[1][N][2];
 
	if (resultL < resultR) {
		result_final = resultL;
		last = 1;
	} else {
		result_final = resultR;
		last = N;
	}
 
	// shop result and path
	printf("%d\n", result_final);
	path(1, N, last);
 
	return 0;
}
 
void recursive() {
	int i = 0;
	int L = 0, R = 0;
	int newQueueEnd = 0;
 
	newQueueEnd = mQueueEnd;
	for (i=mQueueStart; i<mQueueEnd; ++i) {
		L = mQueue[i][0];
		R = mQueue[i][1];
 
		if (L-1 >= 1) {
			EE(L-1, R, 1);
			EE(L-1, R, 2);
 
			mQueue[newQueueEnd][0] = L-1;
			mQueue[newQueueEnd][1] = R;
 
			++newQueueEnd;
		}
 
		if (R+1 <= N) {
			EE(L, R+1, 1);
			EE(L, R+1, 2);
 
			mQueue[newQueueEnd][0] = L;
			mQueue[newQueueEnd][1] = R+1;
 
			++newQueueEnd;
		}
	}
 
	if (mQueueEnd == newQueueEnd) {
		return;
	}
 
	mQueueStart = mQueueEnd;
	mQueueEnd = newQueueEnd;
 
	recursive();
}
 
void EE(int L, int R, int n) {
	int EE_L = 0;
	int EE_R = 0;
 
	int distanceL = 0;
	int distanceR = 0;
 
	int weight = 0;
 
	int resultL = 0;
	int resultR = 0;
 
	// flag
	// 1: take left result
	// 2: take right result
	int flag = 0;
 
	if (n == 1) {
		EE_L = mEE[L+1][R][1];
		EE_R = mEE[L+1][R][2];
 
		distanceL = mDD[L+1][R][1] + D[L+1] - D[L];
		distanceR = mDD[L+1][R][2] + D[R] - D[L];
 
		weight = W[L];
	} else { // n == 2
		EE_L = mEE[L][R-1][1];
		EE_R = mEE[L][R-1][2];
 
		distanceL = mDD[L][R-1][1] + D[R] - D[L];
		distanceR = mDD[L][R-1][2] + D[R] - D[R-1];
 
		weight = W[R];
	}
 
	if (EE_L == INF && EE_R == INF) {
		return;
	}
 
	// which result is better?
	if (EE_L == INF) {
		resultR = EE_R + distanceR * weight;
		flag = 2;
	} else if (EE_R == INF) {
		resultL = EE_L + distanceL * weight;
		flag = 1;
	} else { // EE_L != INF && EE_R != INF
		resultL = EE_L + distanceL * weight;
		resultR = EE_R + distanceR * weight;
 
		if (resultL < resultR) {
			flag = 1;
		} else if (resultL > resultR) {
			flag = 2;
		} else { // resultL == resultR, choose the shorter distance
			if (distanceL < distanceR) {
				flag = 1;
			} else {
				flag = 2;
			}
		}
	}
 
	// save the result of EE(L, R, n), DD(L, R, n) and PP(L, R, n)
	if (flag == 1) {
		mEE[L][R][n] = resultL;
		mDD[L][R][n] = distanceL;
		if (n == 1) {
			mPP[L][R][n] = L+1;
		} else if (n == 2) {
			mPP[L][R][n] = L;
		}
	} else if (flag == 2) {
		mEE[L][R][n] = resultR;
		mDD[L][R][n] = distanceR;
		if (n == 1) {
			mPP[L][R][n] = R;
		} else if (n == 2) {
			mPP[L][R][n] = R-1;
		}
	}
}
 
void path(int L, int R, int last) {
	if (last != M) {
		if (last == L) {
			path(L+1, R, mPP[L][R][1]);
		} else if (last == R) {
			path(L, R-1, mPP[L][R][2]);
		}
	}
 
	printf("%d\n", last);
}
mmx822의 이미지

근데 이게 대학과제라서..
혹시 다른 학우가 이걸보면 안되니까.. 잠시 닫아주시면안될까요?? ㅎㅎ;;
일단 저혼자 이거보고 연구하고 저혼자 짜볼려구요..ㅎㅎ

jick의 이미지

(냉무)

addnull의 이미지

과제라고 미리 말씀해주셨으면 좋을텐데.
제가 더 이상 드릴 말씀은 없습니다.
질문자의 양심에 맡기겠습니다.

mmx822의 이미지

정말 참고만 할겁니다 ㅎㅎ;;
혹시 이거보고 그대로 베끼는 학우가 생길까 우려되어 이렇게 말씀드린건데..죄송합니다..
오늘 쭉 프로그램을 따라가봤더니 어느정도 알겠고.. 제 나름대로 짜볼 생각입니다~
아무쪼록 감사드립니다^^

snowall의 이미지

그정도로 베끼는 것이 문제라면 애초에 질문조차 해서는 안되는 것이었겠죠.

다른 학우들도 이 글을 보고 나름대로 짜볼 수 있는 거잖아요?

피할 수 있을때 즐겨라! http://melotopia.net/b

neocoin의 이미지

마지막 극적 반전이 굉장하네요.

mmx822의 이미지

queue 자료구조를 사용하셨는데..정확히 용도가어떻게되나요??

parkon의 이미지

대학 과제를 이런 식으로 풀어 나가면
정상적인 방법으로 열심히 과제를 푸는 다른 사람들의 점수를 도둑질하는 건데,
그것도 모자라 다른 학우가 보면 안되니까 잠시 닫아 달라고요 ?
그것도 "ㅎㅎ"하는 접미사까지 붙여 가면서요 ?

정말 두번 다시 보고 싶지 않은 글타래 유형이군요.

billiken의 이미지

할말이 없어졌네요..헐..

익명 사용자의 이미지

헐....... 과제...네이버로.....

leboum의 이미지

naver 지식인에게 내공이라도 ...........

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.