[5문제] 완전 탐색 문제풀이 04

백준 7568번

해결 아이디어

완전 탐색을 통해서 키와 몸무게를 비교해야 한다. 이때 키와 몸무게가 모두 비교 대상보다 값이 작을 경우, 등수를 추가해주는 방법으로 문제를 해결하였다.

내가 작성한 코드

num = int(input())
people = [list(map(int, input().split())) for _ in range(num)]

for i in range(num):
    rank = 1
    for j in range(num):
        if people[i][0] < people[j][0] and people[i][1] < people[j][1]:
            rank +=1
    print(rank, end=' ')

백준 1436번

해결 아이디어

1부터 1씩 증가시켜준다. 문자열로 전환해서 '666'이 숫자 안에 있는지 비교하는 것이 주요했다. '666'이 숫자에 존재한다면 count를 증가시켜 주고, count가 N과 같아지면 그 숫자를 출력해주는 방법으로 문제를 해결했다.

내가 작성한 코드

n = int(input())
count = 0
number = 1

while True:
    
    
    if '666' in str(number):
        count +=1
        if count == n:
            print(number)
            break
        
    number+=1

백준 1476번

해결 아이디어

반목문을 돌리면서 서로 다른 범위를 가지고 있는 세 수가 범위를 넘어가는 지점에서 다시 1로 초기화시켜준다. 그리고 주어진 입력 값과 같아질 경우 반복문을 마친다.

내가 작성한 코드

E,S,M = map(int, input().split())
e,s,m,count =0,0,0,0

while True:
   
   if E == e and S == s and M == m:
       print(count)
       break
   else:
       e+=1
       s+=1
       m+=1
       count+=1
       
       if e == 16:
           e = 1
       if s == 29:
           s = 1
       if m == 20:
           m = 1

백준 2503번

해결 아이디어

코드적으로 구현하는 방법이 떠오르지 않기도 했고, 모든 경우의 수를 리스트로 담아야한다는 생각을 미처 하지 못해 오랜시간이 걸렸다. 그래서 타인의 코드를 보고 참고했다.

우선 순열을 사용해서 서로 다른 세 자리수로 구성된 숫자의 모든 경우를 리스트에 담는다. 탐색하는 숫자가 리스트에 담겨있는 숫자내에 있을 때, 인덱스를 통해서 위치가 같으면 스트라이크로 판단하고 아닌 경우 볼로 판단하여 개수를 세준다. 이때 입력 받은 스트라이크, 볼 개수가 카운트한 개수와 맞지 않는다면 그 숫자는 리스트 내에서 제거해준다.

코드

from itertools import permutations

num = int(input())
lst= list(permutations([1,2,3,4,5,6,7,8,9], 3))

for _ in range(num):
    number, s, b = map(int, input().split())
    number = list(str(number))
    removed_count = 0
    
    for i in range(len(lst)):
        s_count = b_count = 0
        i -= removed_count
        
        for j in range(3):
            number[j] = int(number[j])
            if number[j] in lst[i]:
                if j == lst[i].index(number[j]):
                    s_count +=1
                else:
                    b_count +=1

        if s_count != s or b_count != b:
            lst.remove(lst[i])
            removed_count +=1

print(len(lst))

백준 1969번

해결 아이디어

s와 Hamming Distance를 구하는 과정에서 약간의 그리디한 부분이 있었다. s는 Hamming Distance가 가장 작은 DNA이다. 따라서 주어진 N개의 DNA중에서 각 자리에서 가장 많이 위치하고 있는 뉴클레오티드들로만 구성하면 s가 되는 것이다. 그리고 각 자리에서 가장 많이 위치하고 있는 뉴클레오티드를 제외한 뉴클레오티드의 개수를 세어주면 그것이 Hamming Distance의 최소 합이다.

내가 작성한 코드

n,m = map(int, input().split())

dna = [input() for _ in range(n)]
result = ''
hamming_distance = 0

for i in range(m):
    a, c, g, t = 0, 0, 0, 0
    for j in range(n):
        if dna[j][i] == 'T':
            t += 1
        elif dna[j][i] == 'A':
            a +=1
        elif dna[j][i] == 'G':
            g +=1
        elif dna[j][i] == 'C':
            c +=1
    if max(a,c,g,t) == a:
        result += 'A'
        hamming_distance += c+g+t
    elif max(a,c,g,t) == c:
        result += 'C'
        hamming_distance += a+g+t
    elif max(a,c,g,t) == g:
        result += 'G'
        hamming_distance += a+c+t
    elif max(a,c,g,t) == t:
        result += 'T'
        hamming_distance += a+g+c

print(result)
print(hamming_distance)