[Python] 조합 문제 풀이 정리(1)

조합 어렵다..확통 다 까먹음.

조합은 기초를 다질겸 브론즈부터 천천히 올라가겠다.

 

https://www.acmicpc.net/problem/16968

s = input()

if s[0] == 'c':
    answer = 26
else:
    answer = 10

for i in range(1, len(s)): # 연속 판단을 위해 1부터 시작
    if s[i] == 'c':
        if s[i - 1] == 'c':
            answer *= 25
        else:
            answer *= 26
    else:
        if s[i - 1] == 'd':
            answer *= 9
        else:
            answer *= 10

print(answer)

• 연속 문자를 판단하는 것이 중요하다.
• 한번 사용한 문자는 계속 사용할 수 있다.

 

https://www.acmicpc.net/problem/16561

# 정답풀이
n = int(input())//3
print((n-1)*(n-2)//2)

• 등차 수열의 합 공식을 이용한다.
  • n(a+l)//2

n = int(input())//3
cnt = 0
for i in range(1, n+1, 1):
    for j in range(1, n+1, 1):
        if n-i-j>0:
            cnt +=1

print(cnt)

• n과 n을 이루는 수 모두 3으로 나눠서 계산한다(계산 편의를 위해..)
• i와 j(두 수를 합친 값)을 구하고, i와 j가 성립하면(n보다 작으면) 카운트한다.

 

https://www.acmicpc.net/problem/25176

n=int(input())
a=1
for i in range(1,n+1):
  a *= i
print(a)

• 점수가 최솟값일 때 == 각 수가 연속해서 붙어있는 경우
• 즉 n=3이라면, [1,1,2,2,3,3]과 같이 같은 수가 붙어있어야 한다. 같은 두 수를 하나로 본다면 3개의 수를 나열하는 경우의 수(3!)

 

https://www.acmicpc.net/problem/30821

n = int(input())

def factorial(n):
    if n<=0:
        return 1
    
    return n*factorial(n-1)

print(factorial(n)//(factorial(5)*factorial(n-5)))

• 이항계수(조합)문제이다.
• N각형에서 5개의 꼭짓점을 순서를 고려하지 않고 중복 없이 뽑는 경우.

 

https://www.acmicpc.net/problem/12866

# 틀린 풀이
from collections import Counter

n = int(input())
s = list(input())

num_list = Counter(s)
ans = 1
for i in num_list:
    ans *= num_list[i]%1000000007
print(ans)

• Counter()함수를 쓰면 틀린다. 왜지? -> 찾음^^7

반례..!

# 정답 풀이

n = int(input())
s = list(input())

num_list = Counter(s)
ans = 1
k = [0,0,0,0]
for i in s:
    if i=='A':
        k[0]+=1
    elif i=='C':
        k[1]+=1
    elif i=='G':
        k[2]+=1
    else:
        k[3]+=1
for i in range(4):
    ans = (ans*k[i])%1000000007
print(ans)

• 직접 A,C,G,T의 개수를 센다. 나머지 계산 후 저장하기

 

https://www.acmicpc.net/problem/6768

# 정답 풀이
from itertools import combinations
num = int(input())
nums=[]
for i in range(1,num):
    nums.append(i)
combis=list(combinations(nums,3))
print(len(combis))

# 정답 풀이2
a = int(input())
print((a-3) * (a-2) * (a-1) // 6)

• 마지막 득점자는 정해져있으므로 3명의 등번호만 고르면 된다.
• 순서는 오름차순으로 정해져 있기에 순서를 고려하지 않는 combinations를 이용해서 푼다.
• 수가 적어서 가능한 풀이법...그러니까 브론즈인가?

 

https://www.acmicpc.net/problem/14551

# 내 풀이
from itertools import combinations

N, M = map(int, input().split())
num_list = []
for i in range(N):
    num_list.append(int(input()))
ans = 1

for i in num_list:
    if i!=0:
        ans *= i%M
        
print(ans%M)

• 반례 : 0,1 -> 마지막에도 나머지 계산을 해주어야 함.

 

 

https://www.acmicpc.net/problem/14545

n = int(input())
for _ in range(n):
    i = int(input())
    ans = 0
    for j in range(i):
        ans += (i-j)**2
    print(ans)

• 네모의 길이가 4인 경우, 만들 수 있는 네모의 개수는 (4*4 + 3*3 + 2*2 + 1*1)

 

https://www.acmicpc.net/problem/11368

while True:
    C,W,L,P = map(int, input().split())
    if C==W==L==P==0:
        break
    print(C**(W*L*P))

• 가능한 종류는 C^(W*L*P)

 

https://www.acmicpc.net/problem/24606

p1 = input()
p2 = input()

a = 0
for i in range(4):
    if p1[i]!=p2[i]:
        a+=1

if a==0:
    print(1)
else:
    print(2**a)

• 문제를 좀 대충 이해하고 풀었는데...그냥 다른 문자열의 갯수 a를 구하고 2^a를 출력한다. 2^0==1이니까 굳이 if문으로 안나눠도 됐을 듯

 

https://www.acmicpc.net/problem/13987

# 정답 풀이
first_die = list(map(int, input().split()))
second_die = list(map(int, input().split()))
p, q = 0, 0
for i in range(6):
    for j in range(6):
        if first_die[i] > second_die[j]:
            p += 1
        elif first_die[i] == second_die[j]:
            q += 1
print(f'{round(p/(36-q), 5):.5f}')

• 무한 등비 급수...

 

https://www.acmicpc.net/problem/13155

high_num = [0,1,4,7] # 위만 보고 알 수 있는 수
low_num = [0,2,4]
num = [0,4]

n =int(input())
print(4**n*2**n)

• 왼쪽 점수 n자리는 위만 보고 알 수 있어야 하고, 오른쪽 점수 n자리는 위 아래 각각 따로 봐도 알 수 있어야 함.

 

https://www.acmicpc.net/submit/4903

import math

while True:
    a,b = map(int, input().split())
    if a==b==-1:
        break
    n = math.factorial(a+b)//math.factorial(a)//math.factorial(b)
    
    if a+b==n:
        print(str(a)+'+'+str(b)+'='+str(a+b))
    else:
        print(str(a)+'+'+str(b)+'!='+str(a+b))

• 3-2라면, a,a,a,b,b를 나열하는 경우의 수라고 보면 된다.

 

---

# 회고

 

단순 수학 문제들이 많다. 그래도 조합의 기본을 위해...

브론즈 문제라서 그런가? 다국어로 된 문제들이 많아서 그 문제들은 생략함. 필란드어는 좀..못읽겠음;

 

벌써 다음에 배울 문제가 두렵다