1. 2775번 a층 b호에 사는 사람 수 구하기

    결국 못 풀었다… for문 안쓰고 return 재귀함수로 풀려고 쌩쇼하다가 못풀었다…

    for문 써서 다시해보자. 시간을 너무 많이 쓴거같아… 3시간 거의?;;

    # arr[a][b] 만큼 초기화

     arr = [[0] * (b+1) for _ in range(a+1)]

    풀긴했는데 이렇게 푸는게 맞는지 모르겠다.

    DP 방식 같기도 하고 아닌거같기도하고 풀이 좀 집가면서 확인하자…

    Here is the code you provided:

     aseT = int(input())
    
 for _ in range(caseT):
    
     a = int(input())
    
     b = int(input())
    
     # arr[a][b] 만큼 초기화
    
     arr = [[0] * (b+1) for _ in range(a+1)]
    
     for floor in range(len(arr)):
    
         for unit in range(1, b+1):
    
             if floor == 0:
    
                 arr[floor][unit] = unit
    
             else:
    
                 arr[floor][unit] = arr[floor-1][unit] + arr[floor][unit-1]
    
     print(arr[a][b])

    나는 2차원으로 풀었는데 다른 사람들은 굳이 2차원으로 안풀었음…

    1차원 리스트만 가지고 계속 층수 올리는 식으로 갱신함.

    문제를 잘 생각해보면 dp 라고 볼수 있음…

    a층, b호에 사는 사람 수는 a-1 층에 1호부터 b호까지 사는 사람을 다합쳐야한다.

    이 말은 곧

    (a층, b-1호에 사는 사람들 수) + (a-1층, b호에 사는 사람들 수)

    이랑 같다…

    왜냐면 a층, b-1호에 사는 사람들이 a-1층에 1호부터 b-1호까지 사는사람들은 더한 수니까 여기에 a-1층 b호에 사는 사람만 더해주면 깔끔!

     cnt = [i for i in range(1, b+1)]
 # 1층 각 호수에 사는 사람들을 먼저 구해놈.
 # bottom-top의 dp 방식
    
 for floor in range(a):
 	for unit in range(1, b): 
 		cnt[unit] = cnt[unit-1] + cnt[unit]
 		#(a층, b-1호에 사는 사람들 수) + (a-1층, b호에 사는 사람들 수)
 print(cnt[-1])

  2. 11653번 소인수분해 하는 법…

    10분 풀다가 도저히 모르겠어서 검색찬스.

    2학년 때 배운 기억이 난다.

    2에서 시작해서 안 나누어지면 +1 한 3으로 나누어보고 이런식으로 함.

    4로 나누어지면 어떡하나 싶었는데 생각해보니 그랬으면 이미 2로 나누어졌어야했기때문에 4를 소인수 값으로 착각할 일은 없다!

     num = int(input())
 prime = 2
    
 while (num != 1):
     if num % prime == 0:
         print(prime)
         num = num / prime
     else:
         prime += 1

  3. 2309번 일곱 난쟁이의 키 총합이 100 되는 조합 찾기

    하 이것도 어떻게 해야할지 모르겠다…

    dp 같기도하고 sort+더블 포인터 같기도하고…

    9개 중에서 7개 뽑는 방식은 9개 중에서 2개를 뽑는 가짓수와 같다.

    조합 같은 문제 나오면 이런식으로 9C7 → 9C2로 치환해서 생각해보기.

    7개 for문 돌리려니까 막막했는데 2개 뽑는걸로 해결되니까 이중포문으로 하면 끝날듯~

     arr = []
    
 for _ in range(9):
     arr.append(int(input()))
    
 arr.sort()
    
 for i in range(len(arr)-1):
     for j in range(i+1, len(arr)):
         if sum(arr) - (arr[i] + arr[j]) == 100:
             for m in range(len(arr)):
                 if m != i and m != j:
                     print(arr[m])
             exit()
 '''
 풀기는 쉽게 풀었는데 마지막에 exit() 안해줘서
 계속 출력해서 틀려서 답지 봄ㅠㅠ
 3중 포문 너무 못생겨서 찾아보니까
 arr.remove(m) 이런식으로 빼주고 print 하넹
 '''

  4. 1924번 2007년 무슨 요일인지 맞추기

    13분 컷또!

    순회(?)해야될때 쓰는 나머지 개념을 잘 알고 있었기 때문에 맞출 수 있었다.

     month, date = map(int, input().split())
 d = 0
 day = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
    
 if month != 1:
     for m in range(1,month):
         if m in [1, 3, 5, 7, 8, 10, 12]:
             d += 31
         elif m == 2:
             d += 28
         else:
             d += 30
    
 d += date
    
 print(day[d%7])
 '''
 대부분 나처럼 안하고 month도 배열로 총 며칠인지
 다 써놓고 시작하네. if else 안씀ㅋㅋ
 '''

  5. 피보나치 구하기 (재귀가 아닌 dp방식)

    시간은 짧고, 메모리를 크게 줘서 dp로 풀어야되는게 감이 왔다.

    변수 이상하게 한거 못잡아서 10분 허비한거 치곤

    30분 만에 품

    bottom-top 방식으로 풀었음.

    재귀였으면 top-bottom 방식으로 풀었을듯 근데 시간초과 나더라 재귀로 하면

     n =int(input())
 lst = [0 for _ in range(n+1)]
    
 for i in range(n+1):
     if i == 0:
         lst[i] = 0
     if i == 1:
         lst[i] = 1
     else:
         lst[i] = lst[i-1] + lst[i-2]
        
 print(lst[n])
 \#lst[] 말고 dp[] 라고 하자 앞으로^^;;

  6. 11050번 이항계수 구하기

    이항계수가 뭔지 몰라서 못풀겠음;;

    • 이항계수란? 이항식을 전개했을때 나오는 각 항의 계수를 의미함.

      ex) (a+b)^2 = 1a^2 + 2ab + 1b^2

      → 이게 조합 값이랑 같더라…

      2C0, 2C1, 2C2 랑 같음.

     # nCk 조합 값을 구하라는 것과 같은 거였음...
    
 n, k = map(int, input().split())
 num = 1
    
 for i in range(n, n-k, -1):
     num *= i
        
 for j in range(k, 0, -1):
     num /= j
    
 print(int(num))

    내가 아는 조합 계산 하는 법 야매식으로 풀었음

    5C2 = 54 / 21

    원래 공식은

    5C2 = 5! / 2!(5-2)!

    원래 공식대로 풀거였으면 def factorial 선언해서 재귀함수로 만들어서 풀었으면 베스트였을듯.

    5C2 = fact(5) / fact(2)*fact(5-2)

  7. 1934번 최대공약수 구하기

    1일차 때 푼거라 쉽게 풀 줄 알았는데 30분이나 걸림.

    그리고 소스가 왜이렇게 더럽지?;;

    gcd 구하는 걸 def 함수로 뺐어야했는데…

     from sys import stdin
    
 caseT = int(input())
    
 for _ in range(caseT):
     a, b = map(int, sorted(stdin.readline().split()))
     tempA = a
     tempB = b
     while b % a != 0:
         temp = a
         a = b % a
         b = temp
        
     gcd = a
    
     print(tempA*tempB // gcd)
     '''
     a,b의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.
     따라서 나머지가 0이 될때까지 나눌때 그 값이 최대공약수가 된다.
     gcd(a,b) = gcd(a%b, b)
     6, 10 -> 4, 6 -> 2, 4 -> 
     '''

    깔끔한 GCD 함수 ( temp 안쓰고…)

    ==파이썬이 이게 가능한 이유가==

    ==a,b 를 (a, b)의 tuple로 보고 b, a%b 를==

    ==(b, a%b)의 하나의 tuple로 봐서 temp 없이 값 바꿔치기가 된다고 함 ㄷㄷ==

     def gcd(a, b):
     while(b):
         a, b = b, a % b
     return a

    오늘 6개만 풀자고 했는데 7개 풀어서 기분이 좋네요~