10.1~10.3

아직 몇 삽 남았다...

진한 글씨는 풀어낸 문제.

• 못 푼 문제들

  • 9177 단어섞기
  • 1660 캡틴 이다솜 ( 다솜님 죄송합니다 )
  • 17609 회문
  • 1106 호텔
  • 1525 퍼즐 (얘는 반례를 아직 못 찾음)
  • 14244 트리 만들기
  • 9081 단어 맞추기
  • 2078 무한 이진트리

• 복습 겸사겸사

  • 1939 중량제한

  ---

문제 푼 흔적

---

아이디어 정리

9177 단어섞기

dp로도, bfs로도 풀 수 있던 문제. 알듯 말듯 해서 더 시간을 많이 소요했다.

주어진 3개의 문자를 각각 w1,w2,w3라고 하면, 빈 문자열부터 시작해서 인덱스를 점점 늘려가며, 내가 추가하고자 하는 문자와, w3의 문자가 같은지 확인하는 방법으로 문제를 풀면 된다.. (음 어떻게 설명해야 하지)

• dp[0][0]에 T라고 써있는 이유는 빈 문자열은 항상 w3에 포함되어있다고 가정하기 때문이다.

• 파란 부분은 빈 문자열에서 c,a,t 혹은 t,r,e,e 한 문자씩 추가하는 부분이기 때문에, 이전의 상태를 그대로 가져오면 된다.

        dp = [[0] * (length_w2+1) for _ in range(length_w1+1)]
        dp[0][0] = 1
		
        # tree의 경우
        for i in range(1,length_w2+1):
            dp[0][i] = dp[0][i-1] if w2[i-1] == w3[i-1] else 0
	# cat의 경우
        for i in range(1,length_w1+1):
            dp[i][0] = dp[i-1][0] if w1[i-1] == w3[i-1] else 0

그럼 위의 결과처럼 나오게 된다

나머지 부분을 보자.

dp[1][1] , target word에서 현재 비교대상 "a" (w3[1])

추가 될 대상을 비교해보면 a는 t와 c 누구와도 같지 않다.
이렇게 target word의 비교대상과 추가되는 문자 누구와도 같지 않은 경우에는 False를 입력해준다.

이런 식으로 반복 된다면, 우리가 마주하는 케이스는 총 4가지가 되겠다.

• target word의 비교 대상과 추가하고자 하는 문자가 모두 같지 않은 경우
• target word의 비교 대상과 추가하고자 하는 문자가 모두 같은 경우
• target word의 비교 대상과 왼쪽 문자열이 같은 경우
• target word의 비교 대상과 오른쪽 문자열이 같은경우

예... 각각을 그대로 적어주시면 됩니다.

for i in range(1,length_w1+1):
            for j in range(1,length_w2+1):
                if w1[i-1] != w3[i+j-1] and w2[j-1] != w3[i+j-1]:
                    dp[i][j] = 0

                elif w1[i-1] == w3[i+j-1] and w2[j-1] == w3[i+j-1]:
                    dp[i][j] = 1

                elif w1[i-1] == w3[i+j-1] and w2[j-1] != w3[i+j-1]:
                    dp[i][j] = dp[i-1][j]

                elif w1[i-1] != w3[i+j-1] and w2[j-1] == w3[i+j-1]:
                    dp[i][j] = dp[i][j-1]
                   

---

1106 호텔

문제에서 조건으로 주어지는 비용 , 홍보인원 쌍을 딕셔너리에 넣어놓아서 틀린 문제. 비용을 key로 받고 홍보인원이 item이 되니, key가 중복되는 경우를 생각하지 못했다.