검색결과 리스트
CSE/SourceCode에 해당되는 글 4건
- 2005.05.03 길찾기(KOI 2002년 1번) (1)
- 2005.04.25 돌다리 건너기(KOI 2004년도 1번문제)
- 2005.04.20 제목없음
- 2005.04.18 Expressions
글
CSE/SourceCode 2005. 5. 3. 22:09길찾기(KOI 2002년 1번)
#include <stdlib.h>
#include <limits.h>
#define MAX 1000
int A[MAX][MAX];
int T[MAX][MAX];
int L[MAX][MAX];
int R[MAX][MAX];
int N;
int max(int a, int b)
{
return a>b ? a : b;
}
int main(int argc, char *argv[])
{
FILE *ifp;
FILE *ofp;
int i,j;
//데이터 입력부분
ifp=fopen("INPUT.TXT","r");
if(ifp==NULL)
{
fprintf(stdout,""INPUT.TXT" doesn't exit.");
exit(0);
}
fscanf(ifp,"%d",&N);
if(N<5)
{
fprintf(stdout,"N should be, or be greater than 5");
exit(0);
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
fscanf(ifp, "%d", &A[i][j]);
}
fclose(ifp);
L[0][0]=A[0][0];
R[0][0]=INT_MIN;
T[0][0]=L[0][0];
for(i=1;i<N;i++)
{
L[0][i]=L[0][i-1] + A[0][i];
R[0][i]=INT_MIN;
T[0][i]=L[0][i];
}
for(i=1;i<N;i++)
{
L[i][0]=T[i-1][0]+A[i][0];
for(j=1;j<N;j++)
{
L[i][j]=max(L[i][j-1],T[i-1][j])+A[i][j];
}
R[i][N-1]=T[i-1][N-1]+A[i][N-1];
for(j=N-1;j>=0;j--)
{
R[i][j]=max(R[i][j+1],T[i-1][j])+A[i][j];
}
for(j=0;j<N;j++)
{
T[i][j]=max(L[i][j],R[i][j]);
}
}
ofp=fopen("OUTPUT.TXT","w");
fprintf(ofp,"%d
",T[N-1][N-1]);
fclose(ofp);
return 0;
}
트랙백
댓글
-
Tuchy 2005.05.03 22:16
/**************************
1차원배열 사용
**************************/
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
int a[MAX];
int left[MAX];
int right[MAX];
int max[MAX];
int main()
{
int i, j, n;
FILE *fpi, *fpo;
if ((fpi = fopen("INPUT.TXT", "r")) == NULL)
printf("File open failed.
");
else
{
fscanf(fpi, "%d", &n);
for (i = 0; i < n; i++)
max[i] = -10000;
// 0행~(n-1)행까지
for (i = 0; i < n; i++)
{
// i행의 j열의 값을 읽음
for (j = 0; j < n; j++)
fscanf(fpi, "%d", &a[j]);
// 0행의 경우 0열은 a[0], 기타행의 경우 (i-1)행 0열 + a[0]
if (i == 0)
left[0] = a[0];
else
left[0] = a[0] + max[0];
// 1열부터 하나씩 좌항(left)과 상항(upper=max[]) 중 큰 것과 a[j]를 합
for (j = 1; j < n; j++)
{
if (left[j-1] > max[j])
left[j] = left[j-1] + a[j];
else
left[j] = max[j] + a[j];
}
// 0행의 경우 (n-1)열은 a[n-1], 기타행의 경우 (i-1)행 (n-1)열 + a[n-1]
if (i == 0)
right[n-1] = a[n-1];
else
right[n-1] = a[n-1] + max[n-1];
// n-2열부터 하나씩 우항(right)과 상항(upper=max[]) 중 큰 것과 a[j]를 합
for (j = n - 2; j >= 0; j--)
{
if (right[j+1] > max[j])
right[j] = right[j+1] + a[j];
else
right[j] = max[j] + a[j];
}
// 우측부터의 최대합(left)과 좌측부터의 최대합(right) 중 큰 것을 그 행의 max[]로 설정
for (j = 0 ; j < n ; j++)
{
if (i == 0 || i == n - 1 || right[j] < left[j]) // 0행과 n-1행의 경우 우측부터의 합은 불가능하다.
max[j] = left[j];
else
max[j] = right[j];
}
}
}
if ((fpo = fopen("OUTPUT.TXT", "w")) == NULL)
printf("File open failed.
");
else
fprintf(fpo, "%d
", max[n-1]); // 최종항
return 0;
}
글
CSE/SourceCode 2005. 4. 25. 23:05돌다리 건너기(KOI 2004년도 1번문제)
일단 recursion으로 풀었음.
2차원 배열을 만들어서 다이나믹프로그래밍으로 바꾸면
좀더 빨라질 것같음.
***************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
char str[2][MAX];
char substr[MAX];
int func(int stNum,int x, int y)
{
int i;
if(x<y||str[stNum][x]!=substr[y])
{
return 0;
}
else
{
if(y==0 )
{
return 1;
}
else
{
int result=0;
for(i=x-1;i>=0;i--)
{
if(str[(stNum+1)%2][i]==substr[y-1])
result+=func((stNum+1)%2,i,y-1);
}
return result;
}
}
}
int main(int argc, char *argv[])
{
int result=0;
int i,j;
int strlength;
int sublength;
printf("string1 : ");
scanf("%s",str[0]);
printf("string2 : ");
scanf("%s",str[1]);
printf("sub string : ");
scanf("%s",substr);
strlength=(int)strlen(str[0]);
sublength=(int)strlen(substr);
for(i=0;i<strlength;i++)
{
result+=func(0,i,sublength-1)+func(1,i,sublength-1);
}
printf("%d
", result);
return 0;
}
트랙백
댓글
글
CSE/SourceCode 2005. 4. 20. 23:58제목없음
string의 문자들을 순서대로 조합해서
match의 문자열과 같은 문자열을 만들 때,
그 경우의 수를 구하는 문제
예) string : aaaccddd , match : acd 이면
답 : 18
***********************************/
#include <stdio.h>
#include <string.h>
#define MAX 100
char string[MAX];
char match[MAX];
int stringlength=0;
int matchlength=0;
int fun( int x, int y)
{
int i;
if(stringlength-x<matchlength-y) return 0;
if(y==matchlength-1)
{
int cnt=0;
for(i=x;i<stringlength;i++)
{
if(string[i]==match[y])
{
cnt++;
}
}
return cnt;
}
else
{
int sum=0;
for(i=x;i<stringlength;i++)
{
if(string[i]==match[y])
{
sum += fun(i+1,y+1);
}
}
return sum;
}
}
int main()
{
int result;
printf("string을 입력하시오 : ");
scanf("%s",string);
printf("match시킬 문자열을 입력하세요 : ");
scanf("%s",match);
stringlength=(int)strlen(string);
matchlength=(int)strlen(match);
result=fun(0,0);
printf("%d
", result);
return 0;
}
트랙백
댓글
글
CSE/SourceCode 2005. 4. 18. 22:33Expressions
PC/UVa IDs:110604/10157
Coded by tuchy@hanmail.net in 2005.04.18
*******************************************/
// CODE BEGINS//
#include <stdio.h>
#include <stdlib.h>
int func(int, int);
int main(int argc, char *argv[])
{
FILE *ifp;
int length=0;
int depth=0;
if(argc!=2 || (ifp=fopen(argv[1], "r"))==NULL)
{
fprintf(stderr,"Erorr in reading input file!
");
}
while(fscanf(ifp,"%d %d",&length,&depth)!=EOF)
{
printf("%d
",func(length, depth));
}
fclose(ifp);
}
int func(int l, int d)
{
if (l==2*d || d==1)
{
return 1;
}
else
{
return 2*func(l-2,d) + func(l-2,d-1);
}
}
// END OF CODE//
RECENT COMMENT