디시인사이드 갤러리

갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

배열과 포인터를 지나고 두번째 난관에 막혀버렸어요.. 도와주세요

이에갤로그로 이동합니다. 2009.08.28 23:04:17
조회 109 추천 0 댓글 9


알고리즘 공부하고 있습니다..



2차원 배열 경우의 수 구하는 알고리즘을 요즘 풀고 있는데


너무 어렵네요.


하지만 프로그래밍 하는게 싫다거나 하진 않습니다.


좀만 더 하면 이 지옥에서 나갈 수 있을것 같은 묘한 설레임에 계속 열심히 하고 있는데요.


딱히 바로잡아주는 사람 없이 혼자 공부하는거라 너무 힘드네요.



어떻게 해야 할까요??


문제를 풀다보면 제가 쓰는 답이 맞는지 안 맞는지 모르겠어요



문제는 이렇습니다.


Koi4u 2004 모의고사 3. 종이 자르기

 N×M 크기의 격자로 이루어져 있는 직사각형 종이를 자르려고 한다. (N, M은 홀수) 밑의 <그림 1>의 경우에는 N = 3, M = 5 인 경우이며 그림처럼 맨 가운데 칸을 제외한 모든 격자에 정수가 써져 있다.

   p31.gif

가운데 칸을 제외하면, 한번의 가위질로 두 부분으로 종이를 자를 수 있다. 단, 종이를 잘라 생기는 두 직다각형 모양의 종이는 반드시 회전하여 완전히 포갤 수 있어야 한다. 이 경우, 종이를 자르는 방법은 여러 가지가 있을 수 있다.

p32.gif

 

  <그림 2>의 경우는 위의 규칙에 맞게 종이를 자른 예 중 하나를 나타낸 것이다. 이 경우 직다각형 A와 B는 서로 회전하엿을때 완전히 포개진다.

  이 때, 새로 생긴 직다각형에 써져있는 모든 수를 합한 것을 그 직다각형의 점수라고 한다. (점수는 음수가 될 수도 있다.) 이제 해야 할 일은 두 직다각형의 점수의 차를 가장 크게 하는 것이다.

  <그림 2>처럼 잘랐을 때, 직다각형 A의 점수는 2+1+4+5-5+0+9 = 16이고, 직다각형 B의 점수는 7+5-6+3+2-1+1 = 11이다. 따라서 이 경우 점수의 차는 16-11=5가 된다. (이 경우가 최적해는 아니다)

  프로그램 이름은 CUTRECT.EXE 로 하고, 제한 시간은 5초이다.

 

 입력 형식

입력 파일의 이름은 cutrect.in 으로 한다. 첫 줄에 N과 M이 주어진다. N은 5보다 크지 않은 자연수이며, M은 50 이하의 자연수이다. 둘째 줄부터 N+1번째 줄에는 각각 해당하는 직사각형 종이에 써져있는 M개의 자연수가 들어온다. 직사각형 종이에 써져 있는 모든 수는 -100 이상 100 이하 자연수라고 가정하며, 맨 가운데 칸에는 반드시 0이 들어온다고 가정한다. N과 M은 모두 홀수이다.

 

 출력 형식

출력 파일의 이름은 cutrect.out 으로 한다. 첫 줄에 두 직사각형의 점수의 차의 최대값을 출력한다. 모든 답은 signed 32bit 정수형을 넘지 않는다고 가정한다.

 

 입출력 예

입력(cutrect.in)

3 5
2 1 7 5 -6
4 5 0 3 2
-5 0 9 -1 1

 

출력(cutrect.out)

9
 

 

 참고사항

부분점수는 없다.
























저는 휴리스틱(이라고 하나요?? 자세히는 모르겠습니다.)이 뭔지도 모르겠고 사용하는 방법도 몰라서 그냥 단순하게 


모든 가능성을 일일히 최대값과 비교해서 답을 구하는 법 밖에 모릅니다.



그런데 저런 문제들은 모든 가능성을 어떻게 구해야 할 지도 모르겠네요..


직접 손으로 구해보려고 해도 시간이 많이 들어 엄두도 못 내겠구요..





프로그래밍이 너무너무 좋은데 2주일째 이 부분에서 막혀 진행이 안되니 미치겠습니다.



추천 비추천

0

고정닉 0

0

원본 첨부파일 1

댓글 영역

전체 댓글 0
등록순정렬 기준선택
본문 보기

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 연예인 안됐으면 어쩔 뻔, 누가 봐도 천상 연예인은? 운영자 24/06/17 - -
159902 님들아 팝업 창 띄우는 거 좀 알려줭 [4] 오사카(221.153) 09.11.30 70 0
159901 다들 왜 그러셈? 마치 애인없는 사람처럼 [3] ∫ 2t dt=t²+c갤로그로 이동합니다. 09.11.30 135 0
159900 티맥 떡밥.. [5] Pupustory갤로그로 이동합니다. 09.11.30 190 0
159898 숙신횽 봐줘 [5] 김또이(163.152) 09.11.30 88 0
159897 sean횽이나 뇌자알 있는횽들은 봅니다 [5] 애롱(211.252) 09.11.30 97 0
159896 원하는 언어하나 마스터리 vs 09년 신입생이 데쉬 [6] 켁큇갤로그로 이동합니다. 09.11.30 145 0
159895 한번에 핑때려주거나 ip로 변화시켜줄 프로그램없을까 [4] 지지지(61.39) 09.11.30 88 0
159894 티맥스 윈도우가 다음달에 나온다는데 숙신때문이다 [10] 케케켁켁갤로그로 이동합니다. 09.11.30 202 0
159893 에버그린 까지 마라 [4] 고추장불고기갤로그로 이동합니다. 09.11.30 127 0
159892 사무실 인터넷 드디어 고쳤다 [4] 아주아슬갤로그로 이동합니다. 09.11.30 75 0
159891 이제 숙신까는것도 재미없다 케케켁켁갤로그로 이동합니다. 09.11.30 71 0
159890 PMP중에 주식거래할만한 제품 추천해줄 수 업ㅂ나? LaLuna(211.252) 09.11.30 60 0
159888 금연. [3] 유리한갤로그로 이동합니다. 09.11.30 57 0
159887 에버그린 까지말자. 지금이 그럴때냐? [9] 씬입사원갤로그로 이동합니다. 09.11.30 155 0
159886 캐꼬꼬닥님은 봄미다 [5] 연화갤로그로 이동합니다. 09.11.30 96 0
159885 역적 에버그린을 숙청하겠다. [10] 연화갤로그로 이동합니다. 09.11.30 207 0
159883 아이폰 왔쪄염 [3] 온순한감자갤로그로 이동합니다. 09.11.30 125 0
159882 PDA와 컴퓨터 연동에 관한거 [12] 질문자(210.117) 09.11.30 116 0
159881 음 교육원 형들이 IT 를 망쳤다고 생각하지는 않는데. [6] yundream(211.189) 09.11.30 148 0
159879 횽들아 asp 개발툴 질문점.. [3] 암바시술소갤로그로 이동합니다. 09.11.30 325 0
159878 c언어인데 이거 에러나는 이유가 뭐임? [5] 니네집부자(210.110) 09.11.30 139 0
159877 볼랜드 C++ 하고 VC++ 컴파일러 차이가... [4] AutuMn(115.94) 09.11.30 137 0
159876 아 또 한글이 깨진다...짜증난다...ㅠㅠ [1] 캐꼬꼬닭(112.216) 09.11.30 78 0
159875 여느님 만나고 오겠다능 [4] 숙신갤로그로 이동합니다. 09.11.30 176 0
159874 지금까지의 게시물들을 종합해 본다면 .. [2] Pupustory갤로그로 이동합니다. 09.11.30 104 0
159873 주말에 집에서 놀면 뭐하니 [2] 고추장불고기갤로그로 이동합니다. 09.11.30 62 0
159872 ie6 는 진짜 정말로 짜증난다 [1] 캐꼬꼬닭(112.216) 09.11.30 101 0
159871 숙신은 더러운 입을 다물고 자숙하라. [1] 피로토스갤로그로 이동합니다. 09.11.30 88 0
159870 교육원 출신들이 대한민국의 IT를 멍든게 한다고 생각하냐. [3] 개쉛기갤로그로 이동합니다. 09.11.30 164 0
159869 와... 쩌는 탱커 하나 나왔네요. [3] nRST(114.206) 09.11.30 133 0
159868 본격 heart를 소환하는 글 유리한갤로그로 이동합니다. 09.11.30 44 0
159866 고양이 [1] 유리한갤로그로 이동합니다. 09.11.30 64 0
159865 TIG - 인스톨 없이 게임을, 신개념 USB ‘윙’ [1] JuEUS-U갤로그로 이동합니다. 09.11.30 94 0
159863 로또 1등 걸렸으면 좋겠다능 [1] prismatic갤로그로 이동합니다. 09.11.30 54 0
159862 여기 NXT로봇에 대해서 아는형 없어? [4] 히사매갤로그로 이동합니다. 09.11.30 100 0
159861 유리한횽이 솔로가 된게 그냥커피면 [10] 씬입사원갤로그로 이동합니다. 09.11.30 143 0
159860 전공자가 어쩌고 비전공자가 어쩌고. [2] 그런데갤로그로 이동합니다. 09.11.30 129 0
159858 숙신은 도대체 어느 정도의 대역죄인가? [6] prismatic갤로그로 이동합니다. 09.11.30 130 0
159857 횽들 숙신횽 고만까고 이거나 해봐 [2] 연어갤로그로 이동합니다. 09.11.30 67 0
159856 여친 만들려면 차가 있어야 된다는게 레알이얌 ? [5] yundream(211.189) 09.11.30 140 0
159855 천하의 개새끼를 봤나 [9] 개쉛기갤로그로 이동합니다. 09.11.30 154 0
159853 스타할사람? [2] 연화갤로그로 이동합니다. 09.11.30 53 0
159852 숙신횽 진짜 혼자만 그러지말고 AL갤로그로 이동합니다. 09.11.30 96 0
159848 이게 다 숙신때문이다 [4] 케케켁켁갤로그로 이동합니다. 09.11.30 102 0
159847 아 짜증나 숙신 개객기야 [2] 연화갤로그로 이동합니다. 09.11.30 123 0
159846 진짜 4년제 컴공나온 제대로된 프로그래머 드문듯 [11] 구루구루(61.72) 09.11.30 398 0
159845 CS에서는 뭐배우고 CE에서는 뭐배워요? [8] 줏대(76.239) 09.11.30 114 0
159844 web gl [1] prismatic갤로그로 이동합니다. 09.11.30 104 0
159843 길거리에서_가방끈으로.avi [3] 씬입사원갤로그로 이동합니다. 09.11.30 140 0
159841 여친 만든 새퀴가 일도 안 해 에이 나쁜새퀴 [4] 피로토스갤로그로 이동합니다. 09.11.30 124 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2