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

m1njae·2022년 1월 22일
0

5문제

목록 보기
10/14
post-thumbnail

백준 18312번

해결 아이디어

for문을 3개 사용해서 시,분,초를 모두 탐색했다. 문제를 풀 때 00시 00분 00초의 형태가 맞지 않아서 오답이 나왔었다. 그래서 조건문을 통해서 형태를 맞추어주는 작업을 했다.

내가 작성한 코드

N,K = map(int, input().split())

count = 0
for i in range(N+1):
    for j in range(60):
        for k in range(60):
            if str(K) in str(i)+str(j)+str(k):
                count+=1
print(count)

백준 1145번

해결 아이디어

주어진 다섯 개의 자연수 중에서 가장 작은 수를 구한다. 그 수부터 숫자를 1씩 늘려가면서 완전 탐색을 하며 주어진 숫자로 나누었을 때, 나머지가 0이라면 count를 증가시켜준다.

내가 작성한 코드

num = list(map(int, input().split(' ')))
n = min(num)

while True:
    count = 0
    for i in  range(5):
        if n % num[i] == 0:
            count +=1
    if count >= 3:
        print(n)
        break

    n+=1

백준 2160번

해결 아이디어

어떻게 해결해야할지 몰라서 멍 때리는 시간이 많았던 문제이다. 약간의 검색을 통해서 3차원 리스트 형태로 풀이할 수 있다는 힌트를 얻었다. 그림들을 비교할 때는 1번과 2번을 비교하는 경우와 2번과 1번을 비교하는 것이 중복되는 경우이다. 따라서 조합을 활용했다.

파이썬에는 itertools 모듈을 통해서 조합을 쉽게 이용할 수 있다는 것을 알게 되었다. 그리고 KEY 값을 통해서 min()함수에서 값을 비교할 수 있다는 것도 알게 되었다. 오래 걸리긴 했지만, 여러모로 많은 배움이 있었던 문제였다.

내가 작성한 코드

import itertools

n = int(input())
pictures = []

for _ in range(n):
    pic = [list(map(str,input())) for _ in range(5)]
    pictures.append(pic)
    
differ = []

for i in itertools.combinations(range(n),2):
    count = 0
    for a in range(5):
        for b in range(7):
            if pictures[i[0]][a][b] != pictures[i[1]][a][b]:
                count+=1
    differ.append([i[0]+1,i[1]+1,count])

min_differ = min(differ, key =lambda x: x[2])
print(min_differ[0], min_differ[1]) 

백준 2897번

해결 아이디어

몬스터 트럭의 좌표를 점화식 형태로 나타내어서 주차장만큼의 좌표를 완전 탐색했다. 그리고 각 조건에 맞는 조건문을 활용해서 출력하도록 하였다.

내가 작성한 코드

r,c = map(int, input().split(' '))
place = []
for _ in range(r):
    arr= list(map(str, input()))
    place.append(arr)

monster_truck =[]
for i in range(r-1):
    for j in range(c-1):
        monster_truck.append([place[i][j],place[i][j+1],place[i+1][j], place[i+1][j+1]])

result =[0 for _ in range(5)]

for i in range(len(monster_truck)):
        if '#' in monster_truck[i] :
            continue
        elif monster_truck[i].count('.') == 4:
            result[0] +=1
        elif monster_truck[i].count('X') == 1:
            result[1] +=1
        elif monster_truck[i].count('X') == 2:
            result[2] +=1
        elif monster_truck[i].count('X') == 3:
            result[3] +=1
        elif monster_truck[i].count('X') == 4:
            result[4] +=1

for i in range(len(result)):
    print(result[i])

백준 18868번

해결 아이디어

이 문제는 두 우주 행성의 크기 모두 비교하는 것은 비효율적이라고 생각했다. 인덱스를 활용해서 우주 내 행성의 크기를 비교하였고, 두 우주의 인덱스가 동일하다면 두 우주를 균등하다고 판단하는 접근방법으로 문제를 해결하였다.

내가 작성한 코드

m, n = map(int, input().split())
universe = [list(map(int,input().split())) for _ in range(m)]
count = 0

for i in range(m):
    universe_sorted = sorted(universe[i])
    idx = []
    for j in universe[i]:
        idx.append(universe_sorted.index(j)+1)
    universe[i] = idx

for i in range(m-1):
    for j in range(i+1,m):
        if universe[i] == universe[j]:
            count+=1

print(count)
profile
할 수 있는 것부터 차근차근, 항해자의 공부 기록공간

0개의 댓글