U E D R , A S I H C RSS

1R/2016_07_13



1. 오늘의 문제

2. 참가자

  • 15이원준
  • 황창재

3. 코드

3.1. 15이원준


// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
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 n, ans = 0;
		int num[5002];
		int sum[400002] = { 0, };
		scanf("%d", &n);
		for (int i = 0; i < n; i++){
			scanf("%d", &num[i]);
			for (int j = 0; j <i; j++){
				if (sum[200000 + num[i] - num[j]] == 1){
					ans++;
					break;
				}
			}
			for (int j = 0; j < i + 1; j++){
				sum[200000 + num[i] + num[j]] = 1;
			}
		}


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

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

3.2. 황창재


// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <stdio.h>
#include<string.h>

#pragma warning(disable:4996)


void makeSum(int* arr, char* SumAB, int N) {
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = i; j < N; j++) {
			if (SumAB[arr[i] + arr[j] + 200000] > j + 1 || SumAB[arr[i] + arr[j] + 200000] == 0)SumAB[arr[i] + arr[j] + 200000] = j + 1; // 200000 을 기준으로 +,-
		}
	}
}

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

	setbuf(stdout, NULL);

	int TC;
	int test_case;

	int cnt;
	int N;
	int i, j;

	int arr[5000];
	char SumAB[400001];

	scanf("%d", &TC);
	for (test_case = 1; test_case <= TC; test_case++) {
		// 이 부분에서 알고리즘 프로그램을 작성하십시오. 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.

		scanf("%d", &N);

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

		cnt = 0;

		memset(SumAB, 0, 400001);
		makeSum(arr, SumAB, N);

		for (i = 0; i < N; i++) {
			for (j = 0; j < i; j++) {
				if (SumAB[arr[i] - arr[j] + 200000] <= i && SumAB[arr[i] - arr[j] + 200000] != 0) {
					cnt++;
					break;
				}
			}
		}

		// 이 부분에서 정답을 출력하십시오.
		printf("Case #%d\n", test_case);
		printf("%d\n", cnt);

	}

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

4. 아이디어

4.1. 15이원준

  • 숫자 세개를 더한 값들을 저장해 두기 힘들다.
  • a + b + c = d를 a + b = d -c로 생각할 수 있다.이를 이용하면 다음과 같이 알고리즘을 짤 수 있다.
  • i번째 수 - 0~i-1번째 수가 sum에 표시되어있는지 확인한다. 있다면 좋은 수이다.(d - c 확인)
  • i번째 수 + 0~i번째 수의 값들을 sum에 표시해둔다.(a + b준비)

4.2. 황창재

  • a + b = d - c 를 이용
  • a + b 로 만들어질수 있는 모든 수를 체크해둔다.
    이때, a와 b가 몇번째 수까지 좋은수를 만드는데 영향을 줄 수 있는가를 값에 표시해줌
  • d - c 로 만들어질 수 있는 모든 수를 a + b 로 만들어질 수 있는 모든 수에 해당하는게 있는가 확인 및 카운트

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2016-07-14 15:12:05
Processing time 0.0875 sec