9/6 Problem Solving

11657 타임머신 (G4)

 

벨만포드 알고리즘을 수행한다. 거리 배열을 구할 때 데이터 타입 범위에 주의하자. long long을 사용해야 한다.

 

http://boj.kr/5de133d5fa8140b399f4a77308c66fc4

 

 

5052 전화번호 목록 (G4)

 

전화번호들을 사전순으로 정렬한 다음에 인접한 번호끼리 비교한다. 만약에 앞의 번호가 뒤의 번호의 접두어가 된다면 일관성이 없다고 판단할 수 있다.

 

http://boj.kr/42a1be5b39594611bbae780a7ebc36fd

 

 

14852 타일 채우기 3 (G4)

 

dp[n] = 2*n 크기의 벽을 2*1,1*2,1*1 크기의 타일로 채우는 경우의 수

 

그림을 그려보면서 타일의 끝부분에 주목하면 점화식을 유도할 수 있다.

dp[n] = 2*dp[n-1]+3*dp[n-2]+2*dp[n-3]+ ... +2*dp[0]

이 때 O(n^2)으로 테이블을 채우지말고 누적합을 들고 다니면 O(n)으로 답을 구할 수 있다.

 

http://boj.kr/d95c563b23c9451eb30ce585f2258c07

 

 

2571 색종이 - 3 (G3)

 

2D prefix sum으로 구간합을 미리 구해놓는다. 모든 왼쪽 상단점과 오른쪽 하단점 쌍에 대해서 해당 구역이 색종이로 가득 차있으면 직사각형을 만들수 있다고 판단한다. 이 중 최대 넓이를 구해주면 된다.

 

http://boj.kr/d751904b44114906b1906e9e016d94f2

 

 

2281 데스노트 (G3)

 

dp[i] = i번째 이름까지 적었을 때 남은 칸의 제곱합의 최소값

 

이름들을 하나씩 넣어보면서 새로운 줄에 적을지 이어서 적을지 선택한다.

 

http://boj.kr/1df82c2a3d3d439a8ae93f8a83e2bbba