태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

Notice

'Solutions/Mr.K's Solution'에 해당되는 글 70

  1. 2011.08.12 PKU 3074. Sudoku. [판정:TLE](1)
  2. 2011.04.14 PKU 3364. Black and white painting. [판정:AC](1)
  3. 2011.03.23 PKU 3132. Sum of Different Primes. [판정:TLE]
  4. 2011.03.16 PKU 2181. Jumping Cows. [판정:AC](3)
  5. 2011.03.11 PKU 2291. Rotten Ropes. [판정:AC]
  6. 2010.12.31 PKU 3032. Card Trick. [판정:AC]
  7. 2010.10.07 PKU 3085. Quick Change. [판정:AC]
  8. 2010.09.07 PKU 2260. Error Correction. [판정:AC]
  9. 2010.08.29 UVa 341. Non-Stop Travel. [판정:TLE](1)
  10. 2010.05.29 PKU 2844. Sum and Product. [판정:TLE](1)
  11. 2010.05.03 PKU 1422. Air Raid. [판정:RE]
  12. 2010.03.18 PKU 2245. Lotto. [판정:AC](3)
  13. 2010.03.03 PKU 2390. Bank Interest. [판정:AC]
  14. 2010.02.26 PKU 2871. A Simple Question of Chemistry. [판정:AC]
  15. 2010.02.02 PKU 3589. Number-guessing Game. [판정:AC]
  16. 2010.01.28 PKU 2853. Sequence Sum Possibilities. [판정:AC](3)
  17. 2010.01.17 PKU 1989. The Cow Lineup. [판정:TLE]
  18. 2010.01.14 PKU 1989. The Cow Lineup. [판정:WA](2)
  19. 2009.12.25 모두들 메리크리스마스 N 해피뉴이어~ 는 개뿔 -_- PKU 1989. The Cow Lineup. [판정:TLE](2)
  20. 2009.12.23 PKU 1547. Clay Bully. [판정:AC]
  21. 2009.12.21 UVa 562. Dividing Coins. [판정:WA](3)
  22. 2009.12.15 UVa 562. Dividing Coins. [판정:RE](3)
  23. 2009.12.01 PKU 3372. Candy Distribution. [판정:AC]
  24. 2009.11.30 PKU 3372. Candy Distribution. [판정:WA]
  25. 2009.11.20 PKU 3224. Go for Lab Cup! [판정:AC]
  26. 2009.11.18 PKU 3224. Go for Lab Cup! [판정:WA](2)
  27. 2009.09.26 PKU 1547. Clay Bully. [판정:RE](2)
  28. 2009.09.08 PKU 2853. Sequence Sum Possibilities. [판정:TLE]
  29. 2009.09.08 PKU 2000. Gold Coins. [판정:AC](2)
  30. 2009.08.30 PKU 2853. Sequence Sum Possibilities. [판정:TLE](2)
2011.08.12 13:54 Solutions/Mr.K's Solution
ㅋㅋㅋ

너무 정석대로 풀었나
뭔가 빨리 돌리는 방법이 있을텐뎈ㅋ


#include 
using namespace std;

void zeroset( int ary[][9] );
int numfind( int ary[][9], int bry[][9], int wtf );

int find[10]; // 숫자 k(k번째 원소)를 몇개나 찾았는가에 해당하는 배열

int main()
{
	char str[90];
	int a[9][9]; // 풀어야되는 스도쿠
	int b[9][9]; // 메모지
	int i, j;
	int temp;

	while(1)
	{
		gets(str);

		if( strcmp( str, "end" ) == 0 )
		{
			break;
		}

		for( i = 0; i <= 9; i++ )
		{
			find[i] = 0;
		}

		for( i = 0; i < 9; i++ )
		{
			for( j = 0; j < 9; j++ )
			{
				if( str[i*9+j] == '.' )
				{
					a[i][j] = 0;
				}
				else
				{
					a[i][j] = str[i*9+j] - '0';
					find[a[i][j]]++;
					find[0]++;
				}
			}
		}

		while( find[0] < 81 )
		{
			// 스도쿠 연산
			for( i = 1; i <= 9; i++ )
			{
				zeroset( b );
				for( j = 0; j < 2; j++ )
				{
					if( find[i] < 9 )
					{
						temp = numfind( a, b, i );
					}
					if( temp == 0 )
					{
						// 찾는 숫자가 없거나 숫자 대입을 하지 않았으면 함수를 2번 돌릴 필요가 없음
						j++;
					}
				}
			}
		}

		for( i = 0; i < 9; i++ )
		{
			for( j = 0; j < 9; j++ )
			{
				printf( "%d", a[i][j] );
			}
		}
		printf("\n");
	}

	return 0;
}

void zeroset( int ary[][9] )
{
	int i, j;

	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			ary[i][j] = 0;
		}
	}
}

int numfind( int ary[][9], int bry[][9], int wtf ) // wtf : isn't what the fu*k, want to find
{
	int i, j, k, m;
	int esc = 1;
	int count;
	int tempr, tempc;

	// wtf 체크
	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( ary[i][j] == wtf )
			{
				bry[i][j] = 2;
				esc = 0;
			}
		}
	}

	// wtf가 현재 스도쿠에 없음
	if( esc == 1 )
	{
		return 0;
	}

	// wtf가 위치할 수 없는 범위 체크
	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( bry[i][j] == 2 )
			{
				for( k = 0; k < 9; k++ )
				{
					bry[i][k] = 1;
					bry[k][j] = 1;
				}
				for( k = (i/3)*3; k < (i/3)*3+3; k++ )
				{
					for( m = (j/3)*3; m < (j/3)*3+3; m++ )
					{
						bry[k][m] = 1;
					}
				}

				bry[i][j] = 2;
			}
		}
	}

	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( ary[i][j] != 0 && bry[i][j] == 0 )
			{
				bry[i][j] = 1;
			}
		}
	}

	// wtf가 유일하게 들어갈 수 있으면 대입
	for( i = 0; i < 3; i++ )
	{
		for( j = 0; j < 3; j++ )
		{
			count = 0;
			for( k = i*3; k < (i+1)*3; k++ )
			{
				for( m = j*3; m < (j+1)*3; m++ )
				{
					if( bry[k][m] == 0 )
					{
						tempr = k;
						tempc = m;
						count++;
					}
				}
			}

			if( count == 1 )
			{
				ary[tempr][tempc] = wtf;
				find[wtf]++;
				find[0]++;
				esc = 1;
			}
		}
	}

	return esc;
}
 
posted by Milkskin
2011.04.14 22:33 Solutions/Mr.K's Solution



사뿐하게 AC
어려운 문제인줄 알았는데 아니었구만 :)

#include 
using namespace std;

int main()
{
	int n, m, c;
	int temp;

	cin >> n >> m >> c;

	while( (n != 0) || (m != 0) || (c != 0) )
	{
		temp = (n - 7) * (m - 7);

		if( (temp % 2 == 1) && (c == 1) )
		{
			cout << temp / 2 + c << endl;
		}
		else
		{
			cout << temp / 2 << endl;
		}

		cin >> n >> m >> c;
	}

	return 0;
}
posted by Milkskin
2011.03.23 00:44 Solutions/Mr.K's Solution
소점프건은 들보의 코드를 꼼꼼히 읽어보지 않은 내 실수였소 -_-

대충 설명해놓은 뉘앙스라 좀 찜찜하지만, 어쨌든 저게 최상의 풀이인 것 같아 난 손떼기로 ㅋ…
( 일단은 AC 받았기 때문이기도 하고, 가끔은 내가 쓴 코드지만 건드릴 엄두가 안난다 ㅋㅋㅋ )




{ 1000, 10 }에 대한 답을 출력하는데 1분 이상, 5분 이하의 시간이 소요되는듯//
( 엔터쳐놓고 잠깐 보고있다가 이닦고 왔더니 답이 출력되어있어서 그렇게 추정 )

일단 현재 코드는 recursion으로 쓴 상태이고, 
{ 1000, 10 }에 대한 답이 잘 나오는 것으로 보아
이 recursion을 iteration으로 잘 바꾸면 AC 받을듯//

코드는 요 근래 작성한 것 중에 가장 무식하게 작성해놓아서 공개하기가 부끄럽구려 ㅋㅋㅋ
그래도 AC받으면 공개함 ㅋㅋ 
posted by Milkskin
2011.03.16 00:10 Solutions/Mr.K's Solution



정말 간만에 문제를 푼다는 느낌을 제대로 받는구만 ㅋㅋ


그리고 들보자식이 어느정도 사기(?)를 치고 있었다는 것도 알게 되었고//

최근에 올라온 [소점프 ac get] 글은
문제에 나온 예시만 돌려도 답을 얻을 수 없으니까
가급적 빠른 시일 내에 수정하도록 -_-;


// PKU 2181. Jumping Cows

#include 
using namespace std;

int s[150000];
int indexbound;

int calc( int start, int end, int isreverse )
{
	int i;
	int temp;
	int max, maxindex;
	int min, minindex;
	int result = 0;

	max = min = s[start];
	maxindex = minindex = start;
	for( i = start; i <= end; i++ )
	{
		if( max < s[i] )
		{
			max = s[i];
			maxindex = i;
		}
		if( min > s[i] )
		{
			min = s[i];
			minindex = i;
		}
	}

	if( start > end ) { return 0; }

	if( maxindex > minindex && !isreverse )
	{
		if( indexbound < maxindex )
		{
			indexbound = maxindex;
		}
		result += calc( start, maxindex-1, 0 );
		result += calc( maxindex, end, 0 );
	}
	else if( maxindex < minindex && !isreverse )
	{
		result += calc( start, maxindex-1, 0 );
		result += calc( maxindex+1, minindex-1, 1 );
		result += calc( minindex+1, end, 0 );
		result += max - min;
	}
	else if( maxindex > minindex && isreverse )
	{
		result += calc( start, minindex-1, 1 );
		result += calc( minindex+1, maxindex-1, 0 );
		result += calc( maxindex+1, end, 1 );
		result += max - min;
	}
	else if( maxindex < minindex && isreverse )
	{
		result += calc( start, maxindex, 1 );
		result += calc( maxindex+1, end, 1 );
	}
	else if( maxindex == minindex )
	{
		if( indexbound < maxindex )
		{
			indexbound = maxindex;
		}
	}

	return result;
}

int main()
{
	int p;
	int i;
	int height;

	scanf( "%d", &p );

	for( i = 0; i < p; i++ )
	{
		scanf( "%d", &s[i] );
	}

	if( p == 1 )
	{
		printf( "%d\n", s[0] );
	}
	else
	{
		height = calc( 0, p-1, 0 );
		
		// correction
		if( indexbound == 0 )
		{
			height += s[0];
		}
		else
		{
			int i;
			int max, maxindex;
			int min, minindex;

			max = min = s[indexbound];
			maxindex = minindex = indexbound;
			for( i = indexbound; i < p; i++ )
			{
				if( max < s[i] )
				{
					max = s[i];
					maxindex = i;
				}
				if( min > s[i] )
				{
					min = s[i];
					minindex = i;
				}
			}

			if( maxindex == p-1 )
			{
				height += max;
			}
			else
			{
				height += min;
			}
		}

		printf( "%d\n", height );
	}
	
	return 0;
}


풀이를 쓰다가,
내가 만들었던 예시에서 안맞는 부분이 발생하여

일단 풀이는 중단하고 코드만 올려놓았음//

그럼에도 AC가 나온건
아마 pku 서버 내의 테스트케이스를 모두 통과했기 때문이겠지 -_-;;
posted by Milkskin
2011.03.11 23:00 Solutions/Mr.K's Solution

이것은 마치

2차방정식의 극한값(최대값)을 찾는 문제와 같구려 ㄲㄲ

처음에 정렬함수 만들기가 귀찮아서 라이브러리함수 갖다 쓰려고 잔머리 굴렸다가 wa ㅋㅋㅋㅋ


// PKU 2291. Rotten Ropes

#include 
using namespace std;

void bbsort( int *ary, int length )
{
	int i, j;

	for( i = 0; i < length-1; i++ )
	{
		for( j = length-2; j >= i; j-- )
		{
			if( ary[j] > ary[j+1] )
			{
				swap( ary[j], ary[j+1] );
			}
		}
	}
}

int main()
{
	int t;
	int n;
	int w[1000];
	int i;
	int max;

	scanf( "%d", &t );

	while( t > 0 )
	{
		scanf( "%d", &n );

		for( i = 0; i < n; i++ )
		{
			scanf( "%d", &w[i] );
		}

		bbsort( w, n );

		max = 0;
		for( i = 1; i <= n; i++ )
		{
			if( max < i * w[n-i] )
			{
				max = i * w[n-i];
			}
		}

		printf( "%d\n", max );

		t--;
	}

	return 0;
}

아, 하나 덧붙여서

[소 점프]는 열심히 풀고있음 -_-; 알고리즘은 대강 다 만들었고 수정·보완중//
posted by Milkskin
2010.12.31 20:14 Solutions/Mr.K's Solution

문제 자주 못풀어서 미안; -_-a



#include 
#include 

int main()
{
	int n;
	int cards;
	int *linear;
	int i, j;
	int ind;

	scanf( "%d", &n );

	while( n > 0 )
	{
		scanf( "%d", &cards );

		linear = (int *) calloc( cards, sizeof(int) );
		
		ind = 0;

		for( i = 1; i <= cards; i++ )
		{
			j = 0;

			while( linear[ind] != 0 )
			{
				ind = (ind + 1) % cards;
			}

			while(1)
			{
				if( linear[ind] == 0 )
				{
					ind = (ind + 1) % cards;
					j++;
					if( j == i )
					{
						while( linear[ind] != 0 )
						{
							ind = (ind + 1) % cards;
						}

						linear[ind] = i;
						break;
					}
				}
				else
				{
					ind = (ind + 1) % cards;
				}
			}
		}

		for( i = 0; i < cards; i++ )
		{
			printf( "%d%c", linear[i], (i == cards-1)? '\n': ' ' );
		}

		free( linear );

		n--;
	}

	return 0;
}
posted by Milkskin
2010.10.07 23:32 Solutions/Mr.K's Solution

매우 쉬운 문제로군요 '-';

그냥 거스름돈을 잘 거슬러 주기만 하면 됩니다 :D

#include 
using namespace std;

int main()
{
	int n, c;
	int i;

	scanf( "%d", &n );

	for( i = 1; i <= n; i++ )
	{
		int temp;

		scanf( "%d", &c );

		printf( "%d ", i );

		temp = c / 25;
		printf( "%d QUARTER(S), ", temp );

		c -= (temp * 25);
		temp = c / 10;
		printf( "%d DIME(S), ", temp );

		c -= (temp * 10);
		temp = c / 5;
		printf( "%d NICKEL(S), ", temp );

		c -= (temp * 5);
		printf( "%d PENNY(S)\n", c );
	}

	return 0;
}
posted by Milkskin
2010.09.07 23:43 Solutions/Mr.K's Solution



간만에 AC받도록 협조(?)해준 스파킹군에게 심심한 감사를 표하며 ㅋㅋ


원리는 간단합니다

모든 "행의 합"들과 "열의 합"들이 짝수가 나오는 경우
"행의 합"들 중 홀수가 1개, "열의 합"들 중 홀수가 1개 나오는 경우

를 제외하고는 전부 "Corrupt"를 출력해주시면 되겠습니다 :)

#include 
using namespace std;

int main()
{
	int size = 1;
	int rowsum[99];
	int colsum[99];

	while(1)
	{
		int i, j;
		int temp;
		int rowodds, colodds;

		scanf( "%d", &size );

		if( size == 0 )
		{
			break;
		}

		for( i = 0; i < size; i++ )
		{
			rowsum[i] = 0;
			colsum[i] = 0;
		}

		for( i = 0; i < size*size; i++ )
		{
			scanf( "%d", &temp );

			rowsum[ i/size ] += temp;
			colsum[ i%size ] += temp;
		}

		rowodds = 0;
		colodds = 0;
		for( i = 0; i < size; i++ )
		{
			if( rowsum[i] % 2 == 1 )
			{
				rowodds++;
			}
		}

		if( rowodds > 1 )
		{
			printf( "Corrupt\n" );
		}
		else
		{
			for( i = 0; i < size; i++ )
			{
				if( colsum[i] % 2 == 1 )
				{
					colodds++;
				}
			}

			if( colodds != rowodds )
			{
				printf( "Corrupt\n" );
			}
			else if( rowodds == 0 )
			{
				printf( "OK\n" );
			}
			else
			{
				for( i = 0; i < size; i++ )
				{
					if( rowsum[i] % 2 == 1 )
					{
						break;
					}
				}

				for( j = 0; j < size; j++ )
				{
					if( colsum[j] % 2 == 1 )
					{
						break;
					}
				}

				printf( "Change bit (%d,%d)\n", i+1, j+1 );
			}
		}
	}

	return 0;
}
posted by Milkskin
2010.08.29 12:19 Solutions/Mr.K's Solution



STLW2로 이사하고나서 처음 올리는 솔루션인 것 같은데

무식하게 탐색해서 그런지 결국 TLE를 먹었군요 -_-;

#include 
using namespace std;

#define MROUTE 30 // maybe most number of routes

// 1st column is departure, 2nd column is destination, 3rd column is delay
// 90 row are most number of streets
int ary[90][3];
int nost = 0; // number of existing streets

// 1st~10th column are passed intersection list, 11th column is total delay, 12th column is length-1
int route[MROUTE][12];
int used_row = 0;

int intersection;

void push( const int depar, int st_nth, int rt_nth, const int depth );
int findroute( const int departure, int destination, int depth );

int main()
{
	int num = 1;
	int min_delay;
	int mdroute;

	scanf( "%d", &intersection );

	while( intersection != 0 )
	{
		int i, j;
		int nodes; // number of destination
		int depar, desti;

		// input data
		for( i = 1; i <= intersection; i++ )
		{
			scanf( "%d", &nodes );

			for( j = 0; (nodes != 0) && (j < nodes); j++, nost++ )
			{
				ary[nost][0] = i;
				scanf( "%d %d", &ary[nost][1], &ary[nost][2] );
			}
		}
		scanf( "%d %d", &depar, &desti );

		// checking
		findroute( depar, desti, 1 );

		// output data
		min_delay = 10000000;
		mdroute = 0;
		for( i = 0; (route[i][0] != 0) && (i < MROUTE); i++ )
		{
			if( min_delay > route[i][10] )
			{
				for( j = 9; j >= 0; j-- )
				{
					if( route[i][j] != 0 )
					{
						break;
					}
				}

				if( route[i][j] == desti )
				{
					min_delay = route[i][10];
					mdroute = i;
				}
			}
		}

		printf( "Case %d: Path =", num );
		for( j = 0; (route[mdroute][j] != 0) && (j < 10); j++ )
		{
			printf( " %d", route[mdroute][j] );
		}
		printf( "; %d second delay\n", min_delay );

		// new map will be check or terminate program
		scanf( "%d", &intersection );

		if( intersection != 0 )
		{
			for( i = 0; i < nost; i++ )
			{
				ary[i][0] = ary[i][1] = ary[i][2] = 0;
			}
			for( i = 0; i < used_row; i++ )
			{
				for( j = 0; j < 12; j++ )
				{
					route[i][j] = 0;
				}
			}

			nost = 0;
			used_row = 0;
			num++;
		}
	}

	return 0;
}

void push( const int depar, int st_nth, int rt_nth, const int depth )
{
	int i;
	int rt_using = 0;

	if( route[rt_nth][0] == 0 )
	{
		route[rt_nth][0] = depar;
		rt_using = 1;
	}
	if( route[rt_nth][11] < depth )
	{
		route[rt_nth][11] = depth;
	}

	for( i = 0; i < 10; i++ )
	{
		if( route[rt_nth][i] == 0 )
		{
			break;
		}
	}

	route[rt_nth][i] = ary[st_nth][1];
	route[rt_nth][10] += ary[st_nth][2];
	used_row += rt_using;
}

int findroute( const int departure, int destination, int depth )
{
	int i, j, k;
	int sentinel = 0;

	if( depth >= intersection )
	{
		return -1;
	}

	for( i = 0; (ary[i][0] != 0) && (i < nost); i++ )
	{
		if( ary[i][1] == destination )
		{
			if( ary[i][0] == departure )
			{
				push( departure, i, used_row, depth );
			}
			else
			{
				sentinel = findroute( departure, ary[i][0], depth + 1 );

				if( sentinel == -1 )
				{
					sentinel = 0;
					continue;
				}

				for( j = 0; (route[j][0] != 0) && (j < MROUTE); j++ )
				{
					if( route[j][route[j][11]] == 0 )
					{
						for( k = route[j][11]; k > 0; k-- )
						{
							if( route[j][k] != 0 )
							{
								break;
							}
						}

						if( route[j][k] == ary[i][0] )
						{
							push( departure, i, j, depth );
						}
					}
				}
			}
		}
	}

	return 0;
}

탐색 방법은 대강 이런식입니다
만들면서 방법이 조금 바뀌긴 했지만;

글로 쓰려고 했는데 정리가 잘 안돼서 그냥 엑셀로 -_-a (크게해서 보세요)

[sample input #1]


posted by Milkskin
2010.05.29 01:13 Solutions/Mr.K's Solution

으잌ㅋ
3초 안에 답이 안나오는 케이스가 있다닠ㅋㅋㅋ



나 안햌ㅋㅋㅋㅋㅋㅋㅋ


posted by Milkskin
2010.05.03 22:04 Solutions/Mr.K's Solution

RE받은거라서 안올리려고 했는데 ( 만약 RE가 아니었다면 WA였겠지만 )

그냥
블로그 돌아가는 느낌은 내야되니까 올려보아요 :)

알고리즘은 "그래프 자료구조"를 이용했다고 생각하시면 됩니다
실제로 그래프를 구현하지는 않았지만 -_-;


이전 솔루션들과 비교했을 때
변수명이 좀 낯설게 보이실 수 있습니다만

최근에 API 공부할 때 보니, API 책에서 변수명 앞에 알파벳을 붙여주는 것이 좋다고 해서
( 이미 전에도 컴공 조교들한테 들었던 얘기인데 귀찮아서 안했는데, API 책의 예제는 싸그리 그런 형식이라서 어쩔 수 없이 '-' )
나름 그런 형식을 지켜본 것입니다 :)

posted by Milkskin
2010.03.18 00:23 Solutions/Mr.K's Solution
예압

일단 인증 ㄱㄱ요



많이 피곤한 상태에서 졸릴락 말락 하면서 풀었더니 좀 코드가 지저분한 감이 없지 않아 있는 것 같은데

그래도 그냥 올림요 ㅋㅋ



아오 -_-; 졸린데 일찍 자야지
posted by Milkskin
2010.03.03 06:26 Solutions/Mr.K's Solution
선ㅋ빵ㅋ



아침출근이라 안풀리면 어쩌나 걱정했는데
한큐에 끝ㅋ

posted by Milkskin
2010.02.26 11:54 Solutions/Mr.K's Solution

심플하죠 =_=

마지막에 End of Output 출력하는 것만 안 잊어버리면 한방에 AC받았을텐데 -_-;



posted by Milkskin
2010.02.02 02:21 Solutions/Mr.K's Solution

오랜만에 올리는 문제라 일부러 쉬운걸 올렸는지 어쩐지는 몰라도

일단 쉽게 AC -_-;


근데 새로 들어온 분은 문제풀이 하시는거임?
이번달 문제풀이현황 올릴 때 넣을까 말까 정해야되는데 -_-a

그리고 활동 없는사람 2명
정리 할건지 말건지 얘기좀 ㅇㅇ
posted by Milkskin
2010.01.28 18:57 Solutions/Mr.K's Solution



대망의 AC입니다 :D

최근에 나온 문제들 중 몇개는 도통 안풀리길래 잠시 접어두고

전에 풀다 막힌 것들 중 이놈을 다시 잡았습니다


알고리즘에 대한 이야기는 http://studyinglw.tistory.com/587 의 아랫부분에 나와있으니 참고하세요

코딩할 때마다 느끼는거지만 -_-;

어느정도 난이도가 있는 문제는 왠만해선 100줄이 넘어가는군요 -_-;

posted by Milkskin
2010.01.17 03:24 Solutions/Mr.K's Solution
일단, 제 문제해석에 댓글달아주신 milk님 감사합니다 (__)

기존의 알고리즘을 접어두고 이 방법으로 주워먹기하려 했으나



결과는 이렇네요 ㅋㅋ (가장 최근의 2건)

아무래도 소수열을 전부 살펴보는 것이다보니 N이 커지면서 시간이 많이 증가하는듯 합니다
시간 줄이는 방법을 좀 연구해봐야 할듯;

posted by Milkskin
2010.01.14 02:52 Solutions/Mr.K's Solution

스파킹 미안 -_-;
난 이게 한계임



posted by Milkskin
2009.12.25 01:31 Solutions/Mr.K's Solution

흑흑
같이 바람쐬러 나갈 여친 없는 것도 모자라서
저녁에 [군인놈 1명 공익놈 1명 예비역 1명]들과 모여서 술마시기로 했음

더러운 세상 ㅋㅋㅋㅋㅋㅋ



처음의 CE는 main함수의 return type이 void인 탓에 :(

기본 아이디어는 solving process에 올려서 트랙백을 달든지 하겠구요 -_-;

그 아이디어를 바탕으로 처음 끄적거렸던게 아래의 소스이고,




이것을 부분수열의 길이에 상관없이 돌아가도록 반복문으로 바꾸고, 제출한 소스가 아래의 것입니다
(코드 중간에 C언어용 주석(/* */)으로 처리된 부분은 제출할 때 지웠습니다)




천상 TLE 또는 WA를 받을 것 같긴 했지만, 막상 레알로 TLE를 받고 나니 막막하군요 ㅋㅋㅋㅋㅋㅋ

posted by Milkskin
2009.12.23 02:26 Solutions/Mr.K's Solution



최근에 어떤분이 제 [Dividing Coins - RE] 글에다 RE뜨는 이유를 댓글로 적어주셨습니다
그 덕분에 현재 RE에서 WA로 발전한 상태입니다 -_-;


그런데 이것도 같은 이유였더군요 ㅋㅋ

문득 살펴보다가 내가 왜 문제를 제대로 안 읽었을까 하고 반성했다는 :(




다시 환타님과 한문제 멀어졌습니다 ㅋㅋ
posted by Milkskin
2009.12.21 14:02 Solutions/Mr.K's Solution


방금 전까지 몇번을 수정해보고 제출했으나 전부 WA입니다

거의 모든 예외를 처리했다고 생각했는데 뭔가 남아있나봐요 -_-;


(↓실제 제출할 때는 테스트 케이스들은 빼고 제출했습니다)

posted by Milkskin
2009.12.15 15:14 Solutions/Mr.K's Solution


-_-; RE가 뭐하면 뜨는건지 잊어버려서 뭘 고쳐야될지 잘 모르겠음요 ㅋㅋㅋㅋ

활동하는 사람이 없으니 이거 원;




실제 제출할 때는 저 test case 부분은 지우고 냈음//

posted by Milkskin
2009.12.01 00:25 Solutions/Mr.K's Solution


N이 2의 거듭제곱일 때만 yes가 나오는게 맞았군요 -_-;;

문제에서 여러 케이스가 들어온다고 쓰여있었는데
못보고 EOF 처리를 하지 않아서 wa를 받았던 것 같습니다 ㅋㅋㅋ


소스는 올릴까 말까 고민중임요 -_-;;

마지막에 ac받은건 나름 숏코딩으로 줄여본겁니다
C 기준으로 24위에 안착해 있어요 ㅋㅋ
posted by Milkskin
2009.11.30 01:06 Solutions/Mr.K's Solution


처음에는 머리로 그림을 몇번 그려보다가 간단하게 생각해서

1부터 N-1까지( 엄밀히 말하면 0부터 N-1까지 )의 합이 N의 배수가 아니면 무조건 yes, 그 이외에는 no인줄 알고



이렇게 짰다가 한번 wa를 받았고 -_-;


그 다음은 노트에 그림을 직접 그려보면서 체크해봤더니

N이 2의 거듭제곱일 때에 한해 yes가 나오길래 ( 2~12까지 체크해보고, 추가로 16을 체크해봤음 )



이렇게 짰다가 wa를 또 받았습니다 ㅋㅋ
posted by Milkskin
2009.11.20 01:06 Solutions/Mr.K's Solution


몇자 안고치고 끝났네요 -_-;

posted by Milkskin
2009.11.18 00:50 Solutions/Mr.K's Solution


행렬을 사용하지 않고 해볼랬더니 wa가 뜨네요 -_-;

그닥 틀린 부분은 없어보이는데;



winner가 row의 역할을 하고, column이 column의 역할을 하도록 해놓고

각 행의 승수를 합한 뒤 그 승수가 가장 큰 학생의 번호를 저장했다가 출력하도록 만든겁니다//

posted by Milkskin
2009.09.26 01:22 Solutions/Mr.K's Solution


우선,
스파킹군이 dimension을 잘못 번역해놓아서 (고의는 아니었겠지만) 문제의 이해가 다소 어려웠습니다 =_=;

여기선 dimension을 완성된 과제물의 부피로 해석해야 입출력 예시와 들어맞습니다 ㅋㅋ




근데 런타임 에러는 뭐에 문제가 있어야 나오는거였는지 잊어버린 1人 -_-;;

posted by Milkskin
2009.09.08 08:25 Solutions/Mr.K's Solution


ㅋㅋ 이럴수가 :(

인수분해를 하고 나서 그 인수들을 다시 곱하는 방법으로 약수들을 다 구했습니다만 -_-;
(이때, 인수분해를 통해 나온 인수들에 2를 하나 추가해서 구했습니다)

여전히 TLE가 뜨네요 ㅠ (Run ID : 5826748)



posted by Milkskin
2009.09.08 08:14 Solutions/Mr.K's Solution

역시 -_-; 이건 쉬운문제였군요 -_-ㅋ



군수열을 응용하면 간단하게 풀립니다 :)

posted by Milkskin
2009.08.30 12:48 Solutions/Mr.K's Solution


ㅋㅋ 또 TLE입니다 -_-;



첫번째 TLE는 요놈이구요 (Run ID : 5768623)



두번째 TLE는 요놈입니다 -_-; (Run ID : 5781754)




계산해야 하는 수를 M이라고 했을 때

M을 짝수로 나누었을 때는
그 몫이 0.5 단위로 떨어지면 연속된 자연수의 합으로 나타날 가능성이 있는 것이고

M을 홀수로 나누었을 때는
그 몫이 정수로 떨어지면 연속된 자연수의 합으로 나타날 가능성이 있는 것입니다 -_-;

문제에서 예시로 나온 1800의 경우,
인수분해를 하면 2^3 × 3^2 × 5^2 로 분해가 되는데

이 때문에 16으로 나누면 자연스럽게 몫이 0.5 단위로 떨어지게 되고, (112.5)

이 말인 즉슨 112.5 + 112.5 + … + 112.5 (16개) = 1800 과 같은 결과를 줍니다
문제에서 요구하는 것은 연속된 자연수의 합으로 나타낼 수 있는가를 물어보는 것인데

위의 합을 앞부분 8개, 뒷부분 8개로 나누어서
앞부분에서 하나 뒷부분에서 하나를 대응시킨 후, 앞부분에서 0.5단위를 떼서 뒷부분에 붙이면 됩니다


뭔소린고 하니

112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 = 1800
이것을

(112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5) + (112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5) = 1800
이렇게 나누고

(105 + 106 + 107 + 108 + 109 + 110 + 111 + 112) + (113 + 114 + 115 + 116 + 117 + 118 + 119 + 120) = 1800
가운데에서 가까운 놈들끼리 대응시킨 후
각각 0.5, 1.5, 2.5, … 를 떼서 뒷부분에 붙이면 이렇게 됩니다
이러면 문제에서 요구하는 조건에 맞게 되지요 -_-;


홀수로 나눌 때도 1800을 예로 들어보면
일단 3의 배수이니까 3으로 나누어 떨어집니다, 몫은 600이구요

그러면 600 + 600 + 600 = 1800 이 되고, 이것은 곧 599 + 600 + 601 = 1800 을 만들 수 있게 합니다

마찬가지로,
일의 자리가 0이므로 5로 나누어 떨어지겠네요, 몫은 360입니다
이것은 358 + 359 + 360 + 361 + 362 = 1800 을 만들 수 있게 합니다



이런 식으로 찾으면 됩니다만,
위에서 연속된 자연수의 합으로 나타날 가능성이 있다 라고 했습니다 -_-;

위처럼 나누어 떨어져도 문제에서 요구하는 조건에 안맞을 수도 있다는 말이죠 -_-;
그건 직접 찾으시길 ㅋㅋ

posted by Milkskin
prev 1 2 3 next