8/29 Problem Solving

16500 문자열 판별 (G5)

 

dp[i]를 문자열 S의 처음부터 i번째 문자까지의 부분 문자열을 만들 수 있는지를 나타내는 boolean 값으로 정의한다. 초기값으로 dp[0]은 true이다. 이는 빈 문자열을 만들 수 있다는 의미이다. dp[i]를 계산하기 위해 j를 0부터 j-1까지 순회하면서 dp[j]가 true이고 s[j:i]가 단어 목록 A에 포함되는지 확인한다. 만약 그렇다면 dp[i]를 true로 설정한다. 이와 같이 O(N^2)에 테이블을 채울 수 있다. 최종 정답은 dp[n]이다.

 

http://boj.kr/19f69b00d92f4ed2a4162ba4fd28893c

 

 

3987 보이저 1호 (G5)

 

탐사선의 위치에서 위,아래,오른쪽,왼쪽 4방향으로 모두 시그널을 보내본다. 시뮬레이션을 잘 구현하면 된다.

 

http://boj.kr/ac4ac5450efa4b45ba1f92f2de084456

 

 

10529 GREAT + SWERC = PORTO (G5)

 

백트래킹으로 모든 숫자 조합을 만들어 보면서 주어진 식이 성립하는지 확인한다.

 

http://boj.kr/52ae1a8c66ee4a68b31680a5414579cf

 

 

6755 Who is taller? (G5)

 

학생들의 키에 대해서 누가 큰지 관계들이 주어지면 관계들을 방향 그래프로 표현할 수 있다. 그리고 우리가 알고자 하는 관계 p,q가 주어지면 BFS를 이용해서 p에서 q로 도달할 수 있으면 p가 더 크므로 yes, q에서 p로 도달할 수 있으면 q가 더 크므로 no를 출력한다. p,q가 서로 관계 없으면, 즉 각각 다른 컴포넌트에 속해있으면 unknown을 출력한다.

 

http://boj.kr/229b96ae34df49788147a8221f5adbc6

 

 

11975 Build Gates (G3)

 

소들의 지나간 자취가 방향으로 주어진다. 이 때 지나간 자취들에 의해 구역이 나눠지게 된다. 나눠지는 구역의 갯수를 구해야 한다. 2차원 좌표 상에서 자취들을 다 표시해준다음 Flood Fill을 이용해서 답을 구해주면 된다. 이 때 주의할 점은 자취의 시작을 문제의 크기 제한을 넘는 충분히 큰 2차원 공간의 중심에서 시작해야한다. 또한 편의상 한번 이동할 때 2칸씩 이동하여 가장 작은 공간을 세지 않는 일이 없도록 한다.

 

http://boj.kr/54e86b312b0a4f858283cc6f4ed7d3ff