[백준/오늘의 문제] 06.04

난이도	번호	문제 이름
	9933	민균이의 비밀번호
	20364	부동산 다툼
	12865	평범한 배낭
	14391	종이 조각

민균이의 비밀번호

코드

n = int(input())
words = list(input() for _ in range(n))

for word in words:
    if word[::-1] in words:
        print(len(word), word[len(word)//2])
        break

아이디어 & 풀이

입력으로 주어진 비밀번호를 words 리스트에 저장한다.
각 비밀번호를 탐색하면서 만약 거꾸로 표현했을 때 words에 존재한다면, 해당 비밀번호가 답이된다.

---

부동산 다툼

코드

n, q = map(int, input().split())
check = set()
ducks = [int(input()) for _ in range(q)]

# 자식 -> 부모로 거꾸로 올라간다.
# 부모 -> 자식이면 왼쪽 땅, 오른쪽 땅 모두 구분해야 하기때문에 번거로움
for i in range(q):
    duck = ducks[i]
    first_visit_land = 0 # 처음 마주치는 점유된 땅
    
    while duck > 1:
        # 마주치는 점유된 땅 찾기
        # 단, 처음 마주치는 땅을 찾아야하므로 break 하면 안됨
        if duck in check: 
            first_visit_land = duck
        duck //= 2 # 부모 땅으로 이동
    
    # 점유된 땅을 마주치지 않았다면
    if first_visit_land == 0:
        check.add(ducks[i]) # 점유된 땅 추가
    
    print(first_visit_land)

아이디어 & 풀이

✅ 1에서 각 오리가 원하는 땅으로 이동하는 게 아닌, 오리가 원하는 땅에서 1로 이동한다. 즉, 자식 → 부모로 거꾸로 이동한다.

왜냐하면, 1에서 각 오리가 원하는 땅으로 이동할 시, 왼쪽 땅인지 오른쪽 땅인지에 따라 경우의 수를 나눠줘야 하는 번거로움이 존재한다.

✅ 점유된 땅을 마주쳤을 때 바로 while문을 종료하면 안된다.

우리는 거꾸로 올라가고 있기 때문에, 처음 마주친 점유된 땅을 찾아야 한다.
그러므로, 노드 1이 될 때까지 계속해서 올라간다.

제출은 PyPy3로 했다. Python3는 시간초과

---

평범한 배낭

코드

n, k = map(int, input().split())
bags = [list(map(int, input().split())) for _ in range(n)]
dp = [0] * (k + 1)

for i in range(n):
    for j in range(k, bags[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - bags[i][0]] + bags[i][1])
        
print(max(dp))

아이디어 & 풀이

전형적인 dp 문제이다.
이때 주의해야 할 점은 배낭 무게를 탐색할 때 k부터 탐색해야 한다.
만약, bags[i][0]부터 시작한다면 물건의 중복이 발생하여 오답이다.

처음에 bags[i][0]부터 했다가 계속 틀렸다..

---

종이 조각

코드

아이디어 & 풀이

---