[codeup] 코드업 2137 : 자라나라 머리머리 풀이

최종 풀이 코드는 제일 하단에 있다.

 

 일단 블로그 국룰은 헛소리로 시작하는 거기 때문에 헛소리를 시전한다. 프로그래머스 들어가려고했는데 오랜만에 들어가려니 코드업이랑 햇갈려서 잘못 들어갔다. 그런데 내 관심을 끄는 문제가 있어서 문제를 풀기 시작했다. 풀어보니 새로 알게된 점이 많은 문제였던거 같다. 문제도 신선하니 재밌고 배울 포인트도 많으니 한번 풀어보길 추천한다.

 

 

문제 출처 : codeup.kr/problem.php?id=2137

자라나라 머리머리

 

우선 첫시작은 for문을 이용해 O(n)의 복잡도를 갖는 코드를 작성하였다.

n,x를 split를 통해 int, double형으로 각각 받고 문제 그대로 반복을하면서 소수점을 체크하였다.

그런데 O(n)인데도 시간초과가 나서 다른 방버을 시도했다...(오열)

(아 참고로 아래 코드는 for문이 i=0~n-1까지 도는데 문제는 1~n까지의 소수점합이다. 그러나 결국 n/n이나 0/n이나 소수점부분은 동일하기 때문에 문제가 되지 않는다.)

import java.io.IOException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		int n; // 1 ~ 2000 000 000
		double x; // 0.0000 ~ 1000.0000
		
		Scanner scan = new Scanner(System.in);
		String input_str = scan.nextLine();
		
		n = Integer.parseInt(input_str.split(" ")[0]);
		x = Double.parseDouble(input_str.split(" ")[1]);

		double ans = 0.0000;
		
		for(int i=0; i<n; i++) {
			ans += (x*10000.0000 + i * 10000.0000 / n) % 10000;
		}
		
		System.out.println( (int)(ans / 10000)+"."+(int)(ans%10000) );
		
	}
}

 

두번째 시도이다. 여기서 이문제의 첫번째 핵심이 나온다.

n=4 x=1.3000일 경우

1.3 + 1/4 >> 1.55 > 0.55

1.3 + 2/4 >> 1.8 > 0.8

1.3 + 3/4 >> 2.05 > 0.05

1.3 + 4/4 >> 2.3 > 0.3

>> 따라서 총합 : 0.55+0.8+0.5+0.3 = 1.7

이렇게 보면 느낌이 오지 않을것이다.

 

느낌이 오게써보겠다.

1.3 + 1/4 >> 1.55 > 1.55 -1 >0.5

1.3 + 2/4 >> 1.8 > 1.8 -1 >0.8

1.3 + 3/4 >> 2.05 > 2.05 -1 -1 >0.005

1.3 + 4/4 >> 2.3 > 2.3 -1 -1 >0.3

 

자 어느 정도 느낌이 왔는가?? 아직도 느낌이 오지 않는다면 다시 써보겠다

1.3 을 0.3으로 변환

0.3 + 1/4 >> 0.55   > 0.5

0.3 + 2/4 >> 0.8  > 0.8

0.3 + 3/4 >> 1.05 > 1.05  -1 >0.05  <<< check point!!

0.3 + 4/4 >> 1.3 > 1.3  -1 >0.3

 

자 필자는 이렇게 써보았다.

1. 우선 x를 1.3에서 0.3으로 바꿔주었다. > 이문제에서 소수점이 중요하지 x의 정수 부분은 의미가 없기 때문이다.

2. check point가 생겼다. check point를 살펴보자. check point는 x+k/n이 1을 넘는 순간이다.

x<1이고 k/n<=1이므로 x+k/n<2 가 성립한다. 즉 check point 이후에는 x+k/n -1을하면 소수점이 나온다는 얘기다.

그러면 이제 소수점들의 합을 다시 구해본다.

0.5+0.8+0.05+0.3 이 아닌  (0.3+0.3+0.3+0.3) + (1/4 + 2/4 + 3/4 + 4/4) - 1 -1 라고 써보겠다. 자 이제 어느정도 느낌이 왔는가?? 밑줄친 식의 의미를 풀어 써보겠다.

 

1. (0.3+0.3+0.3+0.3)  >> 0.3은 x이고 x는 총 n번 계속해서 나온다.

2. (1/4 + 2/4 + 3/4 + 4/4) >> k/n의 총합들이다. 다 더하면 (n+1)/2 가되는 성질이 있다.

>> 1~n까지의 총합은 n(n+1)/2 이므로 1/n~n/n까지의 총합은 n(n+1)/2 * 1/n이므로 (n+1)/2이다. 물론 나는 고등학교 이후로 수학을 잊고 살아서 문제 풀 때 이게 기억이 안났다. 그래서 이상한 공식을 만들어 사용했다..

3. -1-1 >>이부분은 check point 이후 마다 -1이 붙게되므로 -1들의 총 개수를 구하면된다. n까지 있고 check point가 i번째라고 한다면 -1이 n-i+1개 있는거다.

 

1,2,3번을 정리해서 식으로 쓴다면 x*n+ (n+1)/2 -1*(n-i+1) 이렇게 쓸 수 있다. (i=check point)

i는 for문을 통해 x+k/n>1 일 때를 catch 해보았다.

이를 코드로 작성해보았다.

 

import java.io.IOException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		int n; // 1 ~ 2000 000 000
		double x; // 0.0000 ~ 1000.0000
		
		Scanner scan = new Scanner(System.in);
		String input_str = scan.nextLine();
		
		n = Integer.parseInt(input_str.split(" ")[0]);
		x = Double.parseDouble("0."+(input_str.split(" ")[1].split("\\.")[1]));

		//System.out.println(n);
	
		for(double i=1.0000; i<=n; i++) {
			if( x + i / n >= 1) {
				cal(n, x, i);
				break;
			}
		}
	}
	
	public static void cal(int n, double x, double i){
		if(n%2==0) {
			System.out.println(String.format("%.4f",  x*n - (n-i+1) + (n)/2 + 0.5 ));
		}
		
		else {
			System.out.println(String.format("%.4f", x*n - (n-i+1) + (n-1)/2 +1));
		}
	}
}

 

그런데 이또한 시간초과가 뜬다...결국은 O(n)이기 때문이다... O(n)이면 통과 할줄 알고 자바여서 안된줄 알고 시간 조금만 줄이면 되겠지 생각한 내 실수다... 어떻게 시간을 줄일지 머리를 싸메다가 check point를 반복문이 아니고 식으로 표현 할 수 있지 않을까 생각이 들었다. 바로 구해보았다.

 

x+k/n>=1인 경우 check 포인트이므로

k/n >= 1-x

k >= (1-x)*n 인 때 check 포인트가 된다.

 

(식으로 쓰니깐 훨씬 쉬웠네... 뭔가 숫자들 계속 쓰면서 노가다로 식을 유도했었다... 이렇게 간단한걸)

 

check값 k의 최소값은 결국 (1-x)*n인것이다. 그렇다면 굳이 반복문도 돌필요 없이 이전 코드의 i에 (1-x)*n 살짝만 처리해서 x*n+ (n+1)/2 -1*(n-i+1) 에 넣어주면 끝나는것이다. i값은 정수이므로 i값에 소수가 붙어 있다면 (int)i를 하고 1을 더해준다. 이렇게 코드 작성을 마치고 제출을 하였다. 그런데 문제가 생겼다!!!!!

 

  문제가 생긴 case 이다 input 1000 99.9990 일때

분명히 틀린곳이 없는데 답이 이상하게 나왔다. 모든 값들을 찍어보며 확인을 해주었더니 x=0.999는 정상으로 나오는데

1-x의 값이 이상했다!!! 이것이 바로 컴퓨터의 한계 부동 소수점 오류이다. 아직 제대로 찾아 해결하진 못했지만 설명하자면 컴퓨터는 2진법을 사용하기 때문에 소수점을 완벽하게 표현하지 못한다. 이로 인해 발생하는 문제인거 같다.

java의 경우 x = 0.999 일때 1-x=0.001 이 아닌 1-x = 0.0010000000000000009 가 나온다...!!!!! (으어아아어아아! 개열받음...) 그래서 부동 소수 오류를 잡기 위해 1-x를 구할 때 10000씩을 곱해서 구한다음 10000을 다시 나눠주는 처리를 해주었다.

 

 

 

 

아래는 최종 제출 코드이다.

조금 고칠부분을 말하자면 cal(~~)함수가 짝수 홀수로 나뉘어져 있다. 이를 위에서 구한식 x*n+ (n+1)/2 -1*(n-i+1) 으로 단순히 대체 할 수 있겠다.

import java.io.IOException;
import java.util.Scanner;

public class Main3 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		long n; // 1 ~ 2000 000 000
		double x; // 0.0000 ~ 1000.0000
		
		Scanner scan = new Scanner(System.in);
		String input_str = scan.nextLine();
		
		n = Integer.parseInt(input_str.split(" ")[0]);
		x = Double.parseDouble("0."+(input_str.split(" ")[1].split("\\.")[1]));

		//System.out.println(n);
		
		
		double i= ( (10000-x*10000)/10000*n);
		
		// 부동 소수점 오류 발생 구간 >> ex) x=0.999 1-x=0.0010000000000000009 오류 발생
		System.out.println(x);
		System.out.println(1-x);
		
		if(i > (int)i) i++;
		
		cal(n, x, (int)i);
		
		/*
		for(double i=1.0000; i<=n; i++) {
			if( x + i / n >= 1) {
				cal(n, x, i);
				break;
			}
		}*/
		
	}
	
	public static void cal(long n, double x, long i){
		if(n%2==0) {
			System.out.println(String.format("%.4f",  x*n - (n-i+1) + (n)/2 + 0.5 ));
		}
		
		else {
			System.out.println(String.format("%.4f", x*n - (n-i+1) + (n-1)/2 +1));
		}
	}
}