Project Euler #67 - Maximum path sum II

프로젝트 오일러 67번 - 최대합 경로 두번째 문제
첨부한 파일에서 경로를 따라 가며 숫자를 더했을 때 최대합은?

18번 문제와 완전히 같은 문제. 18번은 숫자가 몇 개 안 되어서 '모든 경로'를 검토할 수 있었지만 여기서는 그게 불가능하다는 정도의 차이.
풀이방법도 18번에서 설명했던 것과 같다.

tri = [map(int, line.strip().split(' ')) for line in open('p067_triangle.txt').readlines()][::-1]

for i in range(1,100):
    for j in range(100-i):
        tri[i][j] += max(tri[i-1][j],tri[i-1][j+1])

print tri[99][0]

0.006초.

Project Euler #66 - 디오판틴 방정식

프로젝트 오일러 66번 - Diophantine equation

1000보다 작은 D 중에서(단, D는 제곱수가 아니다)

x^2 - D y^2 = 1 의 최소정수해 중 x를 가장 크게 만드는 것은?

모든 D에 대해서 x의 최소해를 구해 봐야 한다.

D를 고정하고 x와 y를 늘려가며 찾아보는 건 쉬운데.. 답이 안 나온다. 한참 고민하다가 구글링..

D = 61일 때의 최소해는 x=1766319049, y = 226153980 이라고 한다. brute force는 포기. 인터넷 글을 읽다 보니, 페르마도 풀려다 못 풀었다고 한다. 페르마가 못 푼 문제를 내가 풀 수 있을 것 같지는 않고.. 풀이 방법까지 찾아보게 됐다.

디오판틴 방정식 중에서 특별히 이런 모양의 방정식을 펠방정식 - Pell's equation이라고 부른다는 것도 알게 됐다.

http://en.wikipedia.org/wiki/Chakravala_method#Examples

여기에 있는 풀이 방법을 따랐다. 우변이 ±1, ±2, or ±4 일 때는 좀 더 쉬운 특별한 방법이 있다고 하지만, 그 '특별한 방법'을 쓰지 않아도 iteration을 조금 더 진행하면 답이 나온다고 위키피디아에 친절하게 나와 있다.

#http://en.wikipedia.org/wiki/Chakravala_method#Examples
from math import sqrt

def dio_init(D):
    Di = int(sqrt(D))
    tmpdic = {Di:abs(Di**2-D),Di+1:abs((Di+1)**2-D)}
    a = min(tmpdic,key=tmpdic.get)
    return a,1,a*a-D

def dio_update(a,b,k,D):
    tmpdic = {}
    for m in range(int(sqrt(D))-abs(k),int(sqrt(D))+abs(k)+1):
        if (a + b*m) % abs(k) == 0:
            tmpdic[m] = abs(m*m - D)
    m = min(tmpdic,key=tmpdic.get)
    return (a*m+D*b)/abs(k),(a+b*m)/abs(k),(m*m-D)/k

def dio(D):
    a,b,k = dio_init(D)
    while True:
        a,b,k = dio_update(a,b,k,D)
        if k == 1: return a, b

mx, argmx = 0,0
for D in [x for x in range(2,1001) if x not in [y*y for y in range(1,32)]]:
    if dio(D)[0] > mx: mx = dio(D)[0]; argmx = D

print argmx

ps. x**.5 와 sqrt(x)는 같다. 후자는 from math import sqrt가 필요해서 보통은 0.5제곱하는 쪽을 선호한다. 하지만 가끔, sqrt로 쓰는 게 더 잘 읽히는 날은 sqrt로 쓴다.

psps. 수학이나 알고리즘 공부가 아니라 python 코딩공부를 목적으로 프로젝트 오일러 문제를 풀고 있었다. 이 문제를 접하고 나서 동기부여가 안 된다. 66번에서 그만 두기는 거시기하니까 100번까지 하고 그만 두는 걸로...

Project Euler #65 - e의 수렴

프로젝트 오일러 65번 - convergent of e

e 를 64번 문제와 같은 continued fraction 형태로 표현하면 1,2,1, 1,4,1, 1,6,1, ... 형태로 전개된다. 100까지 전개한 다음 분수로 표현했을 때 분자의 자리수의 합은?

가장 작은 부분부터 차례로 분수를 풀어보면 된다. 이 때 1+1/n 형태를 (n+1)/n 으로 풀거나 뒤집어도 약분되지 않는다. 마음놓고 100번째까지 풀어 보면,

nume,deno=0,1
for k in range(33,0,-1):
    nume,deno=deno,deno+nume
    nume,deno=deno,deno*2*k+nume
    nume,deno=deno,deno+nume
nume = 2*deno+nume
print sum([int(x) for x in str(nume)])

Project Euler #64 - Odd period square roots

프로젝트 오일러 64번 - 제곱근을 분수로 풀었을 때 주기가 홀수인 경우는?

모든 수는 무한분수(continued fraction을 뭐라고 번역하는지 모르겠다)로 표현할 수 있다. 자연수의 제곱근은 continued fraction에서 일정한 주기를 갖는데, 이 주기가 짝수일 수도 있고 홀수일 수도 있다. 10000 이하 자연수 중 주기가 홀수인 경우는 몇 번?

continued fraction은 57번에서 처음 나왔다. 이 때는 대충 넘어갈 수 있었는데, 64번과 그 이후 문제들을 풀려면 continued fraction만드는 법을 제대로 알아야 한다.
문제에서 예로 든 sqrt(23)의 전개가 바로 이해가 되면 good, 그렇지 않으면 아래의 과정을 차근차근 따라가 보는 걸로..
(열심히 타이핑하다가 너무 번거로워서 연습장에 쓰는 걸로.. )

분자, 분모를 뒤집고, 자기보다 작은 가장 큰 수를 찾고, 켤레수를 곱하고, 약분하는 과정을 반복하다가 앞에서 나왔던 것과 같은 패턴을 찾으면 끝.
한가지.. 언제나 약분이 되니까 소인수 분해 과정 거치지 않고 나누어 버렸다.(왜 그런지는 모르겠다)

이걸 코드로 구현하면 이렇게 된다.

from math import sqrt

# (sqrt(a)-b)/c
def findnext(a,b,c):
    h = int(c/(sqrt(a)-b))
    return h, a, h*(a-b*b)/c - b, (a-b*b)/c

def period(n):
    if sqrt(n) == int(sqrt(n)): return 0
    rs = 0
    first = int(sqrt(n))
    a,b,c = (n,first,1)
    while (a,b,c)!=(n,first,1) or rs == 0:
        h,a,b,c = findnext(a,b,c)
        rs+= 1
    return rs%2

result = 0
for i in range(2,10001):
    result += period(i)

print result

실행 시간은 0.35초

Project Euler #63 - powerful digit counts

프로젝트 오일러 63번 - 제곱 자리수 세기
7^5은 5자리, 8^9은 9자리처럼 어떤 수의 n제곱이 n자리가 되는 경우는 총 몇 가지인가?

1^1, 2^1, ... 9^1
1^2 안 되고 ... 4^2 되고.. 9^2까지 모두 되고
4^3 안 되고, 5^3 되고.. 9^3까지 모두 되고
5^4 안 되고...

두 가지 성질..
1. k^n이 되면 k+1, k+2, ... 9까지 다 된다
2. k^n이 되었으면, k^(n+1)부터 체크하면 된다. (n+1)을 위해 1, 2, ... (k-1)은 체크할 필요 없다.

k, n, rs = 1, 1, 0
while k < 10:
    if len(str(k**n)) == n: rs += 10-k; n += 1
    else: k += 1
print rs

실행시간은.. 순식간.

Project Euler #62 - 세제곱 순열

프로젝트 오일러 62번 - cubic permutations

345^3 = 41063625 의 자리수를 바꾸면, 56623104 = 384^3 도 되고, 66430125 = 405^3도 된다. 실제로, 345^3은 이런 성질을 갖는 가장 작은 수이다.
5개의 permutation을 갖는 가장 작은 세제곱수는?


계속 문제가 길어지고 코드는 지저분해져서 재미가 떨어지고 있었는데 오랜만에 쉽게 풀리는 문제를 만났다. 60번, 61번에서 시간을 너무 많이 써서 더 그런 느낌..

그냥 n=1,2,3,4,5.. 에 대해 세제곱수들의 개수를 세다가 5가 되면 return. 단, permutation에 invariant하게 저장해야 하므로 각 자리수의 숫자들을 정렬하여 숫자를 세었다.

n = 1
rs = {}
while True:
    tmp = ''.join(sorted(`n**3`))
    if tmp in rs: rs[tmp].add(n)
    else: rs[tmp] = {n}
    if len(rs[tmp]) == 5:
        print min(rs[tmp])**3
        break
    n += 1

0.05초.
좀 걸리는 부분이 있다. 문제에서 "which exactly five"라고 했는데 위의 코드로는 6개가 되어도 5개 찾은 순간 return하게 된다. 엄밀하게 하려면, 자리수가 바뀌기 전까지 break하지 말고 계속 체크해야 하지만.. five permutations도 매우 드문데, 갑자기 six permutations는 되지 않을 것 같아서 굳이 코드에 넣지 않았다.

Project Euler #61 - cyclical figurate numbers

프로젝트 오일러 61번 - 순환 다항 수
세 숫자 8128, 2882, 8281 는 두가지 독특한 성질이 있다.
1. 두자리씩 끊었을 때 28, 82, 81 이렇게 연결이 되는 성질(cyclical)
2. 8128은 3각수  - n(n+1)/2의 형태, 8281은 4각수 - n^2의 형태, 2882는 5각수 - n(3n-1)/2의 형태태

네자리 숫자 6개로 아래의 성질을 갖는 경우가 단 하나 있다. 이 6개 숫자의 합은?
1. 두자리씩 끊었을 때 연결된다
2. 숫자 6개가 각각 삼각, 사각, 오각, 육각, 칠각, 팔각수


예시에도 있지만 cycle의 순서는 아직 모른다. 3각->4각->5각->... 일 수도 있고, 3각->8각->4각->...일 수도 있다. 순환의 속성상 시작을 어디로 하든 마음대로라는 점은 다행이다. 8각수의 개수가 제일 적으니 거기에서 시작해 보자.
모든 8각수에 대해, 뒤 2자리(꼬리)를 끊고,
이 2자리로 시작하는(머리가 되는) 모든 케이스를 3각~7각에서 찾고
이 때의 꼬리를 찾고,
이 꼬리가 머리가 되는 모든 케이스를 3각~7각 중에서 위에서 선택하지 않았던 곳에서 찾고,
이 때의 꼬리를 찾고,
이 꼬리가 머리가 되는.....
이렇게 3각~7각을 한번씩 돌고 나면 순환이 완성된다.

늘 그렇듯 긴 코드가 실행시간을 줄여준다.

p, ph, pt = [],[],[]

p.append([`n*(n+1)/2`   for n in range(1,200) if 1000 <= n*(n+1)/2   < 10000])
p.append([`n*n`         for n in range(1,200) if 1000 <= n*n         < 10000])
p.append([`n*(3*n-1)/2` for n in range(1,200) if 1000 <= n*(3*n-1)/2 < 10000])
p.append([`n*(2*n-1)`   for n in range(1,200) if 1000 <= n*(2*n-1)   < 10000])
p.append([`n*(5*n-3)/2` for n in range(1,200) if 1000 <= n*(5*n-3)/2 < 10000])
p.append([`n*(3*n-2)`   for n in range(1,200) if 1000 <= n*(3*n-2)   < 10000])

big = {}
#{'10': {0: ['35', '81'],  1: ['24', '89']}, '11': {0: ['28', '76'],  4: ['60']},...}

for i in range(5):
    for e in p[i]:
        head, tail = e[:2], e[-2:]
        if tail[0] != '0':
            if head in big:
                if i in big[head]: big[head][i].append(tail)
                else: big[head][i] = [tail]
            else:
                big[head] = {}
                big[head][i] = [tail]


def prob61(p,big):
    for e5 in p[5]:
        e5h, e5t = e5[:2], e5[-2:]
        if e5t in big:
            for s1 in big[e5t]:
                for h1 in big[e5t][s1]:
                    if h1 in big:
                        for s2 in big[h1]:
                            if s2 not in [s1]:
                                for h2 in big[h1][s2]:
                                    if h2 in big:
                                        for s3 in big[h2]:
                                            if s3 not in [s1,s2]:
                                                for h3 in big[h2][s3]:
                                                    if h3 in big:
                                                        for s4 in big[h3]:
                                                            if s4 not in [s1,s2,s3]:
                                                                for h4 in big[h3][s4]:
                                                                    if h4 in big:
                                                                        for s5 in big[h4]:
                                                                            if s5 not in [s1,s2,s3,s4]:
                                                                                for h5 in big[h4][s5]:
                                                                                    if h5 == e5h:
                                                                                        return int(e5)+int(e5t+h1)+int(h1+h2)+int(h2+h3)+int(h3+h4)+int(h4+h5)
                                                                                    
print prob61(p,big)

0.0015초

Project Euler #60 - prime pair sets

프로젝트 오일러 60번 - 소수짝 세트
3, 7, 109, 673은 각각 소수이면서, 두개씩 짝을 지어 붙여도 항상 소수가 된다. 예를 들어 7109, 1097 은 소수.
이런 성질을 만족하는 소수 5개짜리 세트.. 중 5개 숫자 합이 가장 작을 때?

지금까지 풀었던 문제 중에 가장 어려웠다. 계산 시간도 가장 오래 걸렸고.

4개짜리 세트를 만드는 데 673까지의 소수가 필요했으니.. 5개짜리 세트는 10배쯤 더 필요하지 않나..라고 추측해 본다.
일단 10,000까지의 소수를 모두 찾아둔다.
1200개 정도 되는 소수를 5개씩 묶는 방법은 1200^5 / 5! 너무 크다!
Partitioning해 보자. 3으로 나누어 1이 남는 소수들과 2가 남는 소수들로 나누어 볼 수 있다. 둘이 섞여 버리면 3의 배수가 되어 버리므로 10,000 이하 소수들을 다음과 같이 2개의 그룹으로 나누고, 각 그룹 안에서 5개짜리 세트를 찾으면 된다.
[3] + [x for x in primes_under_10000 if x%3 == 1]
[3] + [x for x in primes_under_10000 if x%3 == 2]

(설명이 좀 더 필요할 듯 하다. 각 자리수의 합이 3의 배수이면 이 수는 3의 배수가 되는 것은 모두 알 테고.. 각 자리수의 합이 3으로 나누어 1이 남는다는 것과 이 수를 3으로 나누었을 때 1이 남게 된다는 것은 동치이다. n 이 각 자리수의 합이 3으로 나누어 1이 남는 수라고 하면 n에서 (n보다 작은) 10^k 를 빼면 3의 배수가 된다. 10^k는 3으로 나누어 1이 남는 수이므로 n = (n - 10^k) + 10^k 는 3으로 나누어 1이 남는다. 같은 방법으로 각 자리수의 합이 3으로 나누어 2가 남는다는 것과 이 수를 3으로 나누었을 때 2가 남게 된다는 것은 동치라는 것을 보일 수 있다.)

아무튼.. 600^5 / 120 도 너무 커서 계산 불가! 다른 방법을 찾아야 한다.

일단 두개씩 비교하는 건 600^2 정도에 가능하니까..
chains라는 dictionary에 i번째 소수와 짝이 될 수 있는(두 개를 붙였을 때 소수가 되는) 소수(의 인덱스)를 저장해 둔다
0:{2,5,7,8,10}
1:{2,5,8,11}
2:{5,7,8,10}
...

그리고 chains안에 있는 0, 1, 2.. loop을 돌면서
{2,5,7,8,10} 에서 4개짜리 세트를 골라내고, (예를 들어, (2,5,8,10)이 뽑혔다면)
{5,8,10}이 chains[2]에 포함되는지 체크한다.
포함된다면, {8,10}이 chains[5]에 포함되는지, 10이 chains[8]에 포함되는지 체크한다.
여기까지 조건을 만족하면 합을 출력한다.

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def chk_pn(n,pn):
    for p in pn:
        if n % p == 0: return False
        if p ** 2 > n: return True

def choose4(lst):
    l = len(lst)
    out = []
    for i in range(l):
        for j in range(i+1,l):
            for k in range(j+1,l):
                for w in range(k+1,l):
                    out.append((lst[i],lst[j],lst[k],lst[w]))
    return out

def prob60(pnt,pn):
    l, chains = len(pnt), {}
    for i in range(l):
        for j in range(i+1,l):
            if chk_pn(int(`pnt[i]`+`pnt[j]`),pn) and chk_pn(int(`pnt[j]`+`pnt[i]`),pn):
                if i in chains: chains[i].add(j)
                else: chains[i] = {j}
    
    for i in chains:
        if len(chains[i]) >= 4:
            for comb in choose4(sorted(list(chains[i]))):
                a,b,c,d = comb
                try:
                    if {b,c,d} <= chains[a] and {c,d} <= chains[b] and d in chains[c]:
                        print pnt[i]+pnt[a]+pnt[b]+pnt[c]+pnt[d]
                except:
                    pass
    

pn = rwh_primes1(10000)
pn1 = [3]+[x for x in pn if x%3==1]
pn2 = [3]+[x for x in pn if x%3==2]

prob60(pn1,pn)
prob60(pn2,pn)

40초..
13 + 5197 + 5701 + 6733 + 8389 = 26033
여러개 나왔으면 그 중 가장 작은 것을 고를텐데, 만 이하 소수들로는 한 세트 밖에 못 만든다.
lowest sum을 찾는 문제니까 (작은수)+(작은수)+(작은수)+(작은수)+(만을 약간 넘는 수) 같은 경우가 답이 될 수도 있다.
2만5천 이하의 소수로 확장해서 다시 돌려보면 될텐데.. 오래 걸리는 걸 돌리기는 귀찮다.

Project Euler #59 - XOR 암호 해독

프로젝트 오일러 59번 - XOR decryption

이진수로 된 문자열 '10011101'을 '0101'이라는 key를 이용해서 XOR 암호화한다고 하자.

우선 앞부분 1001 과 key를 비교하면 1100 이 된다.(XOR은 같으면 0, 다르면 1로 만든다)

뒷부분 1101 과 key를 비교하면 1000 이 된다.

그래서 10011101 을 암호화하면 11001000이 된다. 

같은 방법으로, 11001000 을 '0101'로 XOR연산을 하면, 10011101 이 되어 암호를 풀게 된다.

key가 3자리 소문자 알파벳일 때 첨부한 파일의 암호를 풀고, 풀린 텍스트의 ASCII값을 모두 더하라.

1. 암호를 찾는다.

1) (1,4,7,10, ... 자리의 문자), (2,5,8,... 자리의 문자), (3,6,9,...자리의 문자)를 나눈다. 이들 각각에 대하여,

2) 모든 소문자에 대하여, 암호가 a일 때 '풀린 문자'가 정상적인 영어 알파벳인 개수, ...., 암호가 z일 때... 를 센다. 정상적인 영어 알파벳이 가장 많은 경우를 암호로 본다. 

2. 암호를 푼다.

#ord('A')=>65, ord('Z')=>90, ord('a')=>97, ord('z')=>122, ord(' ')=>32, ord('.')=>46
eng = set(range(65,91)+range(97,123)+[32,46])
encrypted = [int(x) for x in open('p059_cipher.txt').read().split(',')]
passwd = []
for i in range(3):
    enc3=[x for k,x in enumerate(encrypted) if k%3==i]
    tmpdic = {}
    for pw in range(97,123):
        tmpdic[pw] = len([x^pw for x in enc3 if x^pw in eng])
    passwd.append( max(tmpdic, key=tmpdic.get))

decrypted = [x^passwd[k%3] for k, x in enumerate(encrypted)]
#print passwd
#print ''.join([chr(x) for x in decrypted])

print sum(decrypted)

암호는 'god' (103,111,100), 암호화된 본문은 요한복음 1장 앞부분이다.

ord는 22번에서 나왔던 함수.

XOR은 컴퓨터에는 기본적인 연산이라 간단히 쓰는 방법이 있을 듯 했다. 역시나 구글링해보았더니 ^를 쓰면 된다고 한다. 어려워 보였지만, 보기만큼 어렵지는 않았다.

Project Euler #58 - spiral primes

프로젝트 오일러 58번 - 나선형 숫자 배열에서의 소수
5  4  3
6  1  2
7  8  9...
처럼 1부터 나선형으로 숫자를 하나씩 늘려갈 때 대각선에 있는 숫자 중 소수의 비율이 10% 이하가 될 때, 한 변의 길이는?
문제의 예시를 보면, 변의 길이가 7일 때 소수의 비율은 62% 정도이다. 10% 이하로 떨어지려면 꽤 큰 수가 필요할 듯 하다.

변의 길이가 늘어날 때마다 1. 대각선에 추가되는 숫자 네 개가 어떤 것인지 공식을 만들고, 2. 그 숫자들이 소수인지 체크하고, 3. 그 때마다 소수 비율이 10% 이하로 떨어지는지 체크한다.
1. 28번과 같은 문제이다. 오른쪽 아래로 1, 9, 25, 49, ... 패턴을 보이는 데에서 시작하면 된다.
2. 100억을 넘지 않는다고 가정했을 때, a. 100억까지의 모든 소수를 찾아둔다. b. 10만까지의 소수를 찾아두고 이를 이용해서 소수인지 체크한다. 중 b가 메모리 사용이나 속도면에서 더 낫다.
3. 그냥 세면 된다.

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def chk_pn(n,pn):
    for p in pn:
        if n % p == 0: return False
        if p ** 2 > n: return True

chk_N = 100000
pn = rwh_primes1(chk_N)

nprimes = 0
for slen in range(3,chk_N,2):
    if chk_pn(slen*slen - (slen-1),pn): nprimes += 1
    if chk_pn(slen*slen - (slen-1)*2,pn): nprimes += 1
    if chk_pn(slen*slen - (slen-1)*3,pn): nprimes += 1
    if nprimes / (slen*2-1.0) < .1:
        print slen
        break

1.8초. 꽤 큰 숫자까지 체크하는 거니까 이정도로 만족

Project Euler #57 - square root convergents

프로젝트 오일러 57번 - 루트2의 전개
sqrt(2) = 1 + 1 / ( 2 + 1 / ...) 로 전개할 수 있다. 무한전개를 하나씩 끊어서 풀면,
3/2
7/5
17/12
41/29
99/70
...
이렇게 된다. 1000번까지 전개해 보면서 분자와 분모의 자리수가 다른 경우는 몇 번인지 세어 본다.

계산해 보면(또는 관찰해 보면),
뒷분모 = 앞분자+앞분모
뒷분자 = 뒷분모+앞분모

그러면 찾는 것이 어렵지 않다.

n, d, cnt = 3, 2, 0
for i in range(2,1001):
    d, n = d+n, d+d+n
    if len(str(d)) < len(str(n)): cnt += 1

print cnt

Project Euler #56 - powerful digit sum

프로젝트 오일러 56번 - 큰수의 숫자 합
a, b가 각각 100미만일 때, a^b의 각 자리의 수를 모두 더한 값의 최대값은?

a, b를 2부터 99까지 바꿔가면서 모두 계산해 보면 된다.
길게 쓰면,

mx = 0
for a in range(2,100):
    n = a
    for b in range(2,100):
        n *= a
        mx = max(mx, sum([int(x) for x in str(n)]))

print mx

짧게 쓰면,

print max([sum([int(x) for x in str(a**b)]) for a in range(2,100) for b in range(2,100)])

시간은 거의 같다. 각각 0.6초


좀 더 생각해 보면.. 4^8 의 자리수 합보다는 49^89의 합이 훨씬 큰 거다. 그럼 a, b를 2부터 99까지 움직이는 대신 90부터 99까지 움직여봐도 될 것 같다.

print max([sum([int(x) for x in str(a**b)]) for a in range(90,100) for b in range(90,100)])

0.14초. 당연한 얘기지만, 95부터 99까지 체크하는 걸로 바꾸면 더 줄어든다.