백준 2292번 풀이

문제

이 문제는 한줄요약이 안된다… 대충 1번 방에서 n번째 방까지 가는 최단거리를 구하는 문제. 참고로 벌집의 방 수에는 패턴이 있다.

Reference

https://swkang.tistory.com/m/7

계차수열과 근의 공식

왜 이게 나오냐면 내가 이걸로 풀어서요.

계차는 수열의 항과 항 사이의 차이다. 정확히는 뒤의 항에서 앞의 항을 뺀 것이 계차이고, 그 계차들로 이루어진 수열이 계차수열. 즉, 계차수열은 수열이 있어야 성립한다. 개 아니고 계다

계차수열의 일반식은 이걸로 구하고,

계차수열을 이용해 원래 수열의 일반항을 구할 때는 이걸로 구한다.

근의 공식은 이차방정식 ax^2+bx+c=0이 있을 때

이걸로 정의한다. 일단 그래서 또 가져올 코드가 있어요…

import math;
print('2차방정식의 근의 공식은 다음과 같습니다: \n'
      'a, b, c가 실수이며 a<>0일때 이차방정식 ax^2 + bx + c의 해를 구하는 공식 '
      '-b +- 루트(b^2 - 4ac) / 2a');
print('또한 이차방정식의 판별식인 b^2 - 4ac를 이용해 근이 중근인지, 서로 다른 실근인지, 허근인지도 알 수 있습니다. ');
a=int(input('이차항 계수를 입력해주세요 '));
b=int(input('일차항 계수를 입력해주세요 '));
c=int(input('상수항 계수를 입력해주세요 '));
d=(b*b)-(4*a*c);

if d>0:
    print('이 방정식은 서로 다른 두 실근을 가집니다. ');
    e = round((-b + math.sqrt((b * b) - 4 * a * c)) / (2 * a),3);
    f = round((-b - math.sqrt((b*b)-4*a*c))/(2*a),3);
    print(e);
    print(f);
elif d==0:
    print('이 방정식은 중근을 갖습니다. ');
    e = round((-b + math.sqrt((b * b) - 4 * a * c)) / (2 * a),3);
    print(e);
else:
    print('이 방정식은 허근을 갖습니다. ');
    e = (-b / (2 * a));
    f = round(math.sqrt(abs(b * b - 4 * a * c)) / 2 * a,3);
    print(str(e)+'+-'+str(f)+'i');

예전에 이차식의 계수를 입력하면 근의 공식에 대입해서 근을 구해주고, 판별식을 통해 이 방정식의 근이

1. 서로 다른 두 실근(>0)
2. 중근(=0)
3. 허근(<0)

인지도 계산해주는 코드를 짰었는데, 오늘은 이 코드에서 ‘서로 다른 두 실근일 때 양의 실근’을 구하는 공식을 가져올 예정이다.

풀이

일단 코딩에 앞서 일반화를 해야 한다. (마른세수)

이게 그 벌집이다. 보면 되게 중구난방인 것 같지만… 일단 진정하고 아래 그림을 보자.

일단 저기서 1 말고(얘는 방이 하나임) 그 바깥줄부터 보자. …아니 시발점은 보지 말고 종점만 봅시다. 그러면 순서대로 7, 19, 37, 61이다. 아니 이게 무슨 패턴이 있어욧!! 아니 분명 있다니깐여 내가 아까 계차수열 말할 때 뭐 들었음? 계차수열이랑 이게 뭔 상관인지 모르겠다고? 자 그럼 가운데 방부터 시작해서 하나하나 짚어보자. 일단 방의 종점에 대한 수열을 a라고 하면

이렇게 된다.

이렇게 6배수 차이가 난다. 즉, 이 수열은 아무 패턴이 없어보이게 훼이크를 줬지만 계차수열의 초항이 6, 공차가 6인 ‘등차수열’을 이루고 있다.

계차수열의 패턴과 일반화 공식을 이용하면 3n^2-3n+1이라는 식이 도출되게 된다. 그럼 이 다음은? 근의 공식에 대입하면 된다.

씁 뭔가 쎄한데…? 이건 3n^2-3n+1=0일 때의 값이다. 실제로 계산해보면

2차방정식의 근의 공식은 다음과 같습니다: 
a, b, c가 실수이며 a<>0일때 이차방정식 ax^2 + bx + c의 해를 구하는 공식 -b +- 루트(b^2 - 4ac) / 2a
또한 이차방정식의 판별식인 b^2 - 4ac를 이용해 근이 중근인지, 서로 다른 실근인지, 허근인지도 알 수 있습니다. 
이차항 계수를 입력해주세요 3
일차항 계수를 입력해주세요 -3
상수항 계수를 입력해주세요 1
이 방정식은 허근을 갖습니다. 
0.5+-2.598i

이차식의 계수를 그대로 입력하면 허근이 나오는 게 맞다.

2차방정식의 근의 공식은 다음과 같습니다: 
a, b, c가 실수이며 a<>0일때 이차방정식 ax^2 + bx + c의 해를 구하는 공식 -b +- 루트(b^2 - 4ac) / 2a
또한 이차방정식의 판별식인 b^2 - 4ac를 이용해 근이 중근인지, 서로 다른 실근인지, 허근인지도 알 수 있습니다. 
이차항 계수를 입력해주세요 3
일차항 계수를 입력해주세요 -3
상수항 계수를 입력해주세요 -12
이 방정식은 서로 다른 두 실근을 가집니다. 
2.562
-1.562

0이 들어갈 자리에 13을 넣고 이항정리를 하면 이렇게 나온다. (반올림하면 3 맞음) 그럼 이제 IDE를 켜보자.

import sys
a=int(sys.stdin.readline())
# 역시나 유서깊은(?) sys.stdin.readline()입니다. 
# 뭐요.

입력은 역시나 유서깊은 sys.stdin.readline()으로 해 준다.

(-b + math.sqrt((b*b)-4*a*c))/(2*a)

근의 공식 코드에 쓰였던 건 얜데, math가 모듈이다. 그래서 저걸 불러와야 쓸 수 있다. …사실 백준에서 sys말고 뭐 불러본 적이 없음… 아무튼 그럼 제곱근 못써요?

a ** 0.5

걍 지수승에 분수 주면 된다. 일반적으로 루트 끼고 들어가는 제곱근은 1/2승으로 주면 된다.

import sys
a=int(sys.stdin.readline())
# 역시나 유서깊은(?) sys.stdin.readline()입니다. 
# 뭐요. 
c = 1 - a
n = (-(-3) + ((9-12*c) ** 0.5))/6
print(int(n)+1)

그리고 이렇게 한 다음 와 됐다 하고 냈더니 틀렸대. 알고보니 1 넣으면 1이 나와야 하는데 2가 나오는 것이었다

import sys
a=int(sys.stdin.readline())
# 역시나 유서깊은(?) sys.stdin.readline()입니다. 
# 뭐요. 
c = 1 - a
n = -(-(3 + ((9-12*c) ** 0.5))//6)
print(int(n))

일단 연산자를 //로 바꾸고(//는 몫만 나온다. 6//5=1), 저게 음수를 나눌 때는 숫자가 올림이 되기 때문에 참고문헌에서는 음수로 바꾼 다음 나누고 양수로 바꾸셨다. (그리고 형변환은 덤)