백준 #9019 DSLR : 다음 세대에 어떻게 정보를 전달할것인가?

1. 일단 내 풀이는 트리를 통해서 각각의 연산에 대한 DSLR 자손을 만드는 방식이었다. 트리에는 연산의 결과만 저장한다. 트리는 int arr로 구현하였다.

인덱스 n 일때

d 자손 인덱스 = 4*n+1

s 자손 인덱스 = 4*n+2

l 자손 인덱스 = 4*n+3

r 자손 인덱스 = 4*n+4

​

N이 지나온 정보를 알고 싶다면 N % 4로 구할 수 있다. 1이면 d, 2면 s, 3이면 l, 4면 r이 된다.

(N-1)/4 가 N의 부모 노드이므로 이렇게 계속 트리를 타고 올라가면서 연산과정을 역추적할 수 있다.

​

<<<< 문제점 분석

일단 배열이 너무 많이 필요하다.ㅋㅋㅋ 한단계씩 들어갈때마다 4의 지수승으로 개수가 커지다보니,, 감당안됨. 10단계만 들어가도 4의 10승이야ㅋㅋㅋㅋㅋㅋ 오마이갓!

두번째로 다른 연산을 거쳤더라도 같은 숫자가 중복될 수 있다. 이걸 간과했음.

​

2. 정석 풀이

큐 하나, 숫자가 이미 연산에 포함이 됐는지 체크하는 배열 하나가 필요하다.

그냥 연산하고, 숫자 포함됐는지 체크하고, 처음 나온 숫자면 큐에 넣는다.

여기서 문제. 이전세대의 연산과정은 어떻게 전달할것이냐?? 큐에 연산과정을 담은 string을 추가로 넣는 방식으로 해결 가능하다. pair<int, string>을 사용한다. 해결법이 생각보다 단순,,, 출력할 정답도 큐에 같이 넣어주면 되는게 아니었는가..! 굳이 역추적으로 구할 필요는 없다.