U E D R , A S I H C RSS

1R/2016_07_07


1. 오늘의 문제

2. 참가자

  • 박인서
  • 15이원준

3. 코드

3.1. 박인서

#include <iostream>

int main() {
	int TC;
    
	std::cin>>TC;
	for(int j = 1; j <= TC; j++) {
        int n,k,x=0,y=0;
        long long int res=1;
        int a[300001];
        std::cin>>n>>k;
        
        a[0]=0;
        for(int i=1;i<=n;i++) a[i]=a[i-1]+i;
        for(int i=1;i<n;i++) a[n+i]=a[n+i-1]+n-i;
        
        for(int i=0;i<k;i++){
            char c;
            std::cin>>c;
            switch(c){
            case 'U':
                x--;
                break;
            case 'D':
                x++;
                break;
            case 'L':
                y--;
                break;
            case 'R':
                y++;
                break;
            }
            res+=a[x+y];
            if(x+y>=n) res-=(x+y-n+1);
            switch((x+y)%2){
            case 0:
                res+=(y+1);
                break;
            case 1:
                res+=(x+1);
                break;
            }
        }
        
        std::cout<<"Case #"<<j<<std::endl<<res<<std::endl;
	}
	return 0;
}

3.2. 15이원준

* 90점짜리입니다... ㅠ
// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <cstdio>
#include <iostream>
#include<cmath>
using namespace std;

int main(int argc, char** argv) {
	/* 아래 freopen 함수는 input.txt 를 read only 형식으로 연 후,
	앞으로 표준 입력(키보드) 대신 input.txt 파일로 부터 읽어오겠다는 의미의 코드입니다.
	만약 본인의 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면,
	그 아래에서 scanf 함수 또는 cin을 사용하여 표준입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
	또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.
	단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야 합니다. */
	//freopen("input.txt", "r", stdin);

	setbuf(stdout, NULL);

	int TC;
	int test_case;

	scanf("%d", &TC);	// cin 사용 가능
	for (test_case = 1; test_case <= TC; test_case++) {
		// 이 부분에서 알고리즘 프로그램을 작성하십시오.

		int x = 0, y = 0;
		long long int ans = 1;
		int n, k;
		char c;
		scanf("%d %d", &n, &k);
		for (int i = 0; i < k; i++){
			cin >> c;
			switch (c){
			case 'D':
				x++;
				break;
			case 'U':
				x--;
				break;
			case 'L':
				y--;
				break;
			case 'R':
				y++;
				break;
			}
			long long int sum = x + y;
			if (sum < n - 1){
				ans += (1 + sum) * sum / 2;
				if (sum % 2 == 1){
					ans += sum - y + 1;
				}
				else{
					ans += sum - x + 1;
				}
			}
			else{
				ans += (1 + n) * n / 2;
				ans += (3 * n - sum - 1)*(sum - n) / 2;
				if (sum % 2 == 1){
					ans += sum - n + 2 - y;
				}
				else{
					ans += sum - n + 2 - x;
				}
			}
		}


		// 이 부분에서 정답을 출력하십시오.
		printf("Case #%d\n", test_case);	// cout 사용 가능
		printf("%lld\n", ans);
	}

	return 0;	// 정상종료 시 반드시 0을 리턴해야 합니다.
}

4. 아이디어

4.1. 박인서

  • 숫자를 일일이 채워 넣을 수 없다.
  • 홀짝 마다 규칙성을 나눠서 좌표를 넣으면 그 위치에 해당하는 번호를 가르킬 수 있게 만듬.
  • 숫자를 셀 때 대각선에 있는 수의 갯수가 늘어났다가 다시 줄어듦을 잘 확인하여야 됨.

4.2. 15이원준

  • 머리가 나빠서 대각선에 있는 갯수가 1씩 늘어나거나 줄어드는 것과 각 대각선에 있는 좌표의 합이 같은 것을 이용하여 좌표(x,y)의 방 넘버를 구하기 위해 대각선 1번째~대각선 (x+y)-1번째 줄까지 갯수합을 연속된 숫자의 합 구하는 공식을 이용하여 구하고 각 대각선의 첫번째 혹은 마지막번째의 x혹은 y를 이용하여 대각선의 몇번째 숫자이지 구하여 (x,y)의 방 넘버를 구하였다.
  • 이때, n번째 줄 이후에는 줄어든다는 것과 대각선의 몇번째 수인지 구할때 n번째 이후에는 그냥 x와 y만을 이용하면 안되는 것과 n번째 이후의 대각선에서 (x+y)-1번째 줄까지의 합 구하는 것을 좀 더 생각해 보아야한다.
  • 무엇이 잘못되었을까 난 90점을 받았다...ㅂㄷ
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2016-07-07 17:07:40
Processing time 0.0101 sec