글 읽기 - 대체 어떻게 풀어야하죠??

takeclassic 6년 전 0

값이 너무 커서 배열조차 못 쓰는 것 같던데,

메모리를 안 쓰고 이걸 풀 수 가 있을까요...??

어떤 방식으로 해야 하는지 감이 안오네요.

고수분들 힌트좀 주세요 ㅠㅠ

저는 아래 방식으로 풀어보려고 했습니다.

import java.util.Scanner;

public class Eye_1637 {
	
	static int [] arr = new int[2147483647];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int biggest=0;
		int N = sc.nextInt();
		for(int i=0;i<N;i++){
			int a= sc.nextInt();
			int l = sc.nextInt();
			if(l>biggest)
				biggest = l;
			int d = sc.nextInt();
		
			for(int j=1;j<=l;j++){
				if(a+(d*j)<=l){
					arr[a+(d*j)] +=1;
				}
			}
		}
		for(int i=1;i<=biggest;i++){
			if(arr[i]%2!=0){
				System.out.println(i + " " + arr[i]);
			}
		}
	
		
	}
}

chogahui05 6년 전 6

f(x) = 정수 묶음에서 x이하의 수가 나온 갯수.

예를 들어서 문제에 있는 input 같은 경우 정수 묶음이

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5

6 7 8 9 10

이렇게 나오잖아요?

f(1) = 2

f(2) = 4

...

이런 식으로 쓸 수 있죠.

여기까지만 힌트 드릴게요.

takeclassic 6년 전 0

우와 이런 규칙은 대체 어떻게 찾으신 거죠?

뭔가 이론적 배경이 있는 건가요? 아니면 그냥 감각으로 찾으신건가요?

아직도 갈 길이 머네요 저는

chogahui05 6년 전 4

문제가 쉬운 편은 아닙니다. 사실..

중상 ~ 상 정도 되는 문젠거 같은데요. 딱히 이론적인 배경은 없고요.

a와 b가 자연수라고 하면

a가 2로 나누어 떨어지는 경우에

a*b도 2로 나누어 떨어집니다만. c가 홀수인 경우

a*b+c는 2로 나누어 떨어지지 않죠. 이걸 구현한 것 뿐입니다. 사실 저도 첨에 헤메긴 했습니다.

cokcjswo 6년 전 0

홀수개 존재하는게 딱 하나 있다 혹은 없다.

있다면, 홀수개 존재하는놈을 기준으로 경계값을 설정할 수 있다.

이분탐색할 수 있다.

재밌는 문제네요 ~

chogahui05 6년 전 2

언제부터 이 문제를 푼 사람이 많아졌을까요?? 허허..

소문이 많이 났나 보군요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

대체 어떻게 풀어야하죠??

takeclassic 6년 전 0

chogahui05 6년 전 6

takeclassic 6년 전 0

chogahui05 6년 전 4

cokcjswo 6년 전 0

chogahui05 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말