문제

100

77

75

74

5

4

474747

474747

내 풀이:

#

브루트포스 6번째 문제만에 드디어 itertools를 찾아서 쓰게 되었다. 

4랑 7의 중복조합으로 만들 건데 한자릿수부터 6자릿수까지 따로 생각을 해서 조합을 구한다. 

그다음에 뭐 리스트를 정수형으로 만들고 큰 수부터 하나씩 n이랑 비교해서 n이랑 같거나 작아지는 순간 i를 출력한다.

#

이거는 백준 파이썬 기준 맞힌사람 2241명 중에서 열 번째라고 나오니까 뭔가 잘한 것 같음. 근데 뭐가 잘한 건지는 모르겠다.

#

다른 사람의 신기한 풀이

입력값 n부터 1 씩 빼가면서 모든 숫자가 4또는 7이 나올 때까지 for문을 돌리는 것이다. 내가 한 것처럼 하면 조합이랑 n이랑 비교하니까 비교할 게 많지는 않은데 이건 n부터 시작해서 모든 수, 그리고 그 수 안의 모든 자릿수를 살펴봐야 하니까 오래 걸리긴 할 것 같다.

20
7
23
19
10
15
25
8
13

7
8
10
13
19
20
23

내 풀이:

a=0

arr=[]
   
for i in range(9):
    b=int(input())
    arr.append(b)
    a+=b
   
c=a-100

for i in arr:
    for j in arr:
        if i+j==c and i!=j:
            arr.remove(i)
            arr.remove(j)
    if len(arr)==7:
        break
       

arr.sort()
for i in arr:
    print(i)

#

무려 다섯 번 틀리고 맞아버렸다. 

난쟁이 키 아홉 개중에서 합이 100이 되는 7개를 골라서 작은 순서대로 출력하는 문제.

#

한 줄에 한 명 씩, 아홉 개의 키를 입력 받고 a에 그 합을 저장. 

c는 a에서 얼마나 빠져야 100이 되는지, 그니까 빠져야 하는 난쟁이 둘의 키의 합을 의미함. 

아홉 중 돌아가면서 두 명 고르고 키 더해서 c와 같고 각각의 원소가 서로 다른 수면 두 명을 뺌. 

(여기서 고른 건 예외 없이 모든 조합을 돌았으니까 중복순열로 볼 수 있음)

(원래 했어야 하는 건 걍 조합.그러면 i!=j가 필요 없어지고 두 수가 순서만 바꿔서 다시 조합되는 중복도 없어짐)

근데 서로 다른 수를 더해서 c가 나오는 조합이 두 개 이상일 수 있으니 첫번째 조합이 빠지면 바로 전체 for문을 종료함.

arr 오름차순으로 배열하고 원소 한 줄에 한 개씩 출력

#

처음 두 번은 런타임 에러가 났는데 프린트 부분을

for i in range(7):
    print((sorted(arr))[i]) 이렇게 적어서 그렇다. 형식 오류인 듯하다.

#

그 다음에 세 번 더 틀린 이유

for i in arr:
    for j in arr:
        if i+j==c and i!=j:
            arr.remove(i)
            arr.remove(j)
            break

만약에 두 수의 합이 c인 값 두 개를 찾아서 리스트에서 제거를 했다면, 바로 안쪽 for 문을 탈출함. 그럼 바깥쪽 반복문이 남으니까 다음 i값에 대해서 j값이 처음부터 대입되고... 만약에 더해서 c가 나오는 조합이 두 개 이상이면 7난쟁이가 이미 됐는데도 난쟁이가 더 빠질 수 있음.

for i in arr:
    for j in arr:
        if i+j==c and i!=j:
            arr.remove(i)
            arr.remove(j)
        break

이건 그냥... 안쪽 for문에서 j한개 대입하면 if문 충족하든말든 안쪽 for문이 종료됨. 그러면 다음 i값으로 넘어가서 다시 첫번째 j를 대입하고 if문에 상관없이 바로 다음 i값으로 넘어가고... 의 반복.

for i in arr:
    for j in arr:
        if i+j==c and i!=j:
            arr.remove(i)
            arr.remove(j)
    if len(arr)==7:
        break

정답이 출력되는 코드: 그냥 c찾았다고 break를 하지 말고, 만약에 난쟁이가 7명이 되면 그때 안쪽, 바깥쪽 for문을 같이 break하겠다. 라는 코드이다. 

끝.

n = 9
arr = [int(input()) for _ in range(n)]
arr.sort()
 
for i in range(n):
    for j in range(i+1, n):
        if sum(arr) - (arr[i] + arr[j]) == 100:
            for k in range(9):
                if i == k or j == k:
                    continue
                print(arr[k])
            exit()
 
print('\n'.join(map(str, arr)))

# 

남의 풀이 1

n = 9
temp1, temp2 = 0, 0
arr = [int(input()) for _ in range(n)]
 
for i in range(n):
    for j in range(i+1, n):
        if sum(arr) - (arr[i] + arr[j]) == 100:
            temp1 = arr[i]
            temp2 = arr[j]
 
arr.remove(temp1)
arr.remove(temp2)
 
print('\n'.join(map(str, sorted(arr))))

#

남의 풀이 2

import itertools
arr = []

for i in range(9):
    arr.append(int(input()))

for i in itertools.combinations(arr,7):
  if sum(i) == 100:
    for j in sorted(i):
        print(j)
    break

#

남의 풀이 3

엄청 많은 사람들이 itertools로 풀었다. 여기서는 조합 combination을 써먹으면 됨. 이건 어제 배웠으니 앞으로 잘 써먹어야겠다.

60
100

245
64

75
80

-1

내 풀이:

#

m,n을 정수형으로 입력받음. M과 N은 10000이하의 자연수 이므로, 

1부터 100까지의 자연수 i에 대해서 i*i가 m이랑 n사이에 있으면 arr이라는 리스트에 i의제곱수를 넣음.

리스트에 있는 수들의 합과 최솟값 출력

#

지금 보니까 이것도 합 구할 떄 sum(map(int,str(i)))이거 썼어도 됐겠다.

# 다른 사람 풀이

m,n을 정수형으로 입력 받음.

1로 시작하는 i의 제곱이 b보다 작거나 같은 동안, 그게 a보다 크거나 같으면 num이라는 리스트에 i의 제곱수를 넣음.

( i*i라고 하는 대신 이 사람은 i**2라 표혔했음. 제곱하는 수가 커질 수록 저렇게 하는 게 맞긴 함. )

그리고 if조건을 만족시키든 그렇지 않든, while문 한번 돌 때마다 i에 1씩 더함. 

만약 while문이 끝났는데 num이라는 리스트에 원소가 하나도 없으면 -1을 출력, 그게 아니라면 합과 최솟값을 출력.

#

이렇게 하면 시간이 좀 덜 걸리는 이유가 뭘까?

1부터 101까지 다 안 보고 m보다 큰 수 나오면 while문이 끝나서?

그럼 나처럼 굳이 for문을 써야겠다면 range를 1,n 이렇게 했으면 훨씬 간단할 뻔했다. (if문 조건도 간단해지니까)

sum함수도 이제 쓸 수 있으면 써야겠다.

#

이건 제곱수를 구한 게 아니라 m과 n의 제곱근을 구하는 방식. 음... 문제 조건에 입력값 범위가 명시되어있지 않았다면 이렇게 해야할 것 같다.

m과 n 사이의 수에 대하여 i의 제곱근은 root

i가 root의 제곱과 같다면 num리스트에 append해라? 이게 이해가 안됐는데 이제 알았다.

출력은 뭐 다 비슷하게 했다.

216

198

내 풀이:

#

0부터 n까지의 자연수에 대하여,,

각 자릿수를 원소로 하는 리스트로 만든다. 초기값 0인 a에다가 각자릿수를 하나씩 더하는 게 안쪽 for문의 내용이고, for문이 끝나면 각 자릿수의 합a에다가 그냥 i라는 숫자 그대로를 더해서 그게 n이랑 같다면 출력하고 b에 1 더하고 바깥쪽 for문에서 벗어나기.

만약 b가 0이면(한번도 생성자 출력 안했으면) 0을 출력한다.

쉽다고 생각하고 풀었다가 생성자 없는 경우 조건을 안 봐서 틀렸다. 문제는 잘 읽자 

#

다른 사람들보다 출력시간?이 개오래걸리는데 이유를 알아보자.

#

쪼끔 더 빨리 돌아가는 다른 사람의 풀이

#

다른 사람이 푼 엄청 빨리 출력되는 풀이

일단 생성자는 a와 b사이에 있다고 먼저 설정함. a는 n에서 자릿수만큼 9를 뺀 값이고, b는 그냥 int(n)이다.

그래서 a와 b사이에서 조건을 만족하는 생성자가 나오면 그 값을 프린트한 후 바로 for문 종료(최솟값 구하는 거니까)

만약 a부터 b-1까지 다 돌았는데 생성자가 안 나왔으면 i=b-1일 것이다. 그러면 그냥 0을 출력함.

#chat gpt가 알려준 차이점

내 코드:

0부터 n까지의 모든 수에 대해 조건을 검사하고 조건을 만족하는 값을 찾아내기

0부터 n까지 모든 수에 대해 반복문을 돌리고 각 수마다 자릿수를 분리하고 더하는 작업 등 복잡한 연산을 수행

반복문 안에서 다른 조건문을 사용하여 조건을 만족하는 값을 찾으면 바로 반복문을 종료하고 출력하는데,

이는 검사해야 하는 모든 수에 대해 조건을 검사하는 작업을 줄여주기 때문에 조금 더 최적화된 코드 구조?

마지막 코드:

주어진 조건을 만족하는 값을 찾아내기

입력 값 n에 대해서 범위를 제한하여 반복문을 돌림

각 숫자에 대해 연산을 수행하는 데 필요한 작업이 상대적으로 적음

5 21
5 6 7 8 9

21

10 500
93 181 245 214 315 36 185 138 216 295

497

내 풀이:

#

n,m은 숫자로, 카드에 적힌 수는 리스트로 입력받는다.

arr 안의 임의의 세 원소의 합이 m보다 작거나 같고, 세 수 모두 다른 수이면 arr_2라는 새로운 리스트에 그 합을 추가한다.

for문을 끝까지 돈 뒤 arr_2 리스트의 중복을 제거하고 거꾸로 정렬(=내림차순 됨)한 후 0번째 원소를 출력

#

i,j,k를 있는대로 다 더하면 세 수 모두 다를 때~라는 조건을 추가해야 하는데 i보다 큰 j, j보다 큰 k만 더하겠다고 하면 자동으로 조합의 경우의 수만 구할 수 있다.

#남의 풀이 1

#

나랑 비슷한 방식으로 했는데 조건을 만족하는 수중에 최댓값을 구하는것까지 for문에 넣어버렸다.

위의 내 풀이보다 시간이 6분의 1밖에 안 걸렸는데 왜일까? 내 풀이는 있는 조건 만족할 때마다 append하는 시간, 리스트 sort하고 reverse하는 시간이 더 걸리는 거 아닐까

#

위에서 말한 범위 지정방식을 사용해서 장황한 조건을 안 써도 되는 코드이다.

# itertools 조합을 이용한 남의 풀이

#

이거 풀때는 itertools 라이브러리를 몰랐는데 3가지 카드로 이루어진 조합을 구한 다음에 조합끼리 더한 거랑 m을 비교하고 있다. 훨씬 간단한 방법인 건맞는데 그 형식 바꾸고 그런 걸 잘 다뤄야 할 수 있는 방법이다. 이사람은 sum이랑 max까지 써서 엄청 간단해보인다.

6 3

3

25 4

0

2735 1

1

내 풀이:

#

n 과 k를 한 줄에 입력 받음.

for 문으로 1부터 n까지 모든 수를 n으로 나눠봐서, 나머지가 0인 애들은 리스트 a 에 원소로 추가함. 

리스트 a의 k번째 값을 프린트 함.

#

k번째로 작은 수는 리스트의 k+1번째에 있기 때문에 처음에 a의 첫번째 원소로 0을 넣어놓았다. 

그리고 0이 출력되도록 하는 경우에도, length가 k보다 작은 게 아니라 리스트에서 0을 제외한 length가 k보다 작아야 하므로 -1을 해 주었다. 

(이렇게 하지 말고 마지막에 print(a[k-1])을 하면 된다.. 근데 +1인지 -1인지 헷갈려서 그렇게 하지 않았다)

# 남의 풀이

K번째 약수를 구하는 거니까 자연수를 1부터 N까지 넣으면서 약수가 나올 때마다 K-1을 했다. 

K가 0이 되면 A에 i 를 넣고 for문을 끝냄. 만약 k가 0이 안되면? (약수의 개수보다 k가 더 크면?) 그냥 A(0)을 출력한다.