The Way
5월 13일 백준 본문
* 코드는 맨 아래에 있습니다
갑자기 급 게을러졌다. 13일에 7시간을 못채우니 14일은 그냥 어영부영 아무것도 안하고 날려버렸다.
나태함은 만악의 근원이다. 나태해지지 말고 항상 노력해야겠다.
# 백준 14501번: 퇴사
기초적인 DP 문제인데 약간 헷갈렸다.
일은 그 날이 시작할 때 받고, 퇴사는 그 날 저녁에 하는 것에 유의.
즉, 1일짜리 일을 n일에 받았어도 그 일을 끝내고 퇴사할 수 있는 것이다.
# 백준 1890번: 점프
기초적인 DP 문제. 문제를 잘못읽어서 약간 헤맸다.
0이 나올 때 주의하자.
# 백준 1965번: 상자넣기
머여 이거 LIS잖어
# 백준 1309번: 동물원
# 백준 1937번: 욕심쟁이 판다
# 백준 2096번: 내려가기
기초적인 DP 문제
# 백준 6359번: 만취한 상범
# 백준 9507번: Generations of Tribbles
생략
# 백준 2225번: 합분해
중복조합을 구하는 문제.
식은 n, k가 주어졌을 때 경우의 수는 $\binom{n + k - 1}{n}$가지이다.
메모리를 할당할 때 앞부분 가능 범위가 n + k - 1이므로 대략 400까지 줘야 한다.
# 백준 11054번: 가장 긴 바이토닉 부분 수열
lis랑 약간 달라서 당황할수도 있는데, lis + 역방향 lis 두개 더하고 1을 빼주면 된다.
# 백준 1915번: 가장 큰 정사각형
처음에는 이차원 최대 부분 합과 동일한 알고리즘을 사용해 코딩했다.
$O(n^3)$인 것이 살짝 불안했지만, 시간 내에는 풀릴 것 같아서 짰더니 성공했다.
다 풀고 다른 사람 것을 보니 끝내주는 점화식이 보여 재작성해보았다.
점화식은 rec[i][j] = i, j를 오른쪽 아래로 하는 최대 정사각형이라 했을 때,
1이면 rec[i][j] = min(rec[i - 1][j], min(rec[i][j - 1], rec[i - 1][j - 1])) + 1이 성립한다는 것이다. (0이면 당연히 0)
# 백준 10942번: 팰린드롬?
s, e에 대해 팰린드롬 여부를 저장해놓으면, 최대 $n^2$번 비교해보면 된다.
# 백준 2011번: 암호코드
문제가 압권이다. 선영: 구해보자! 부분이 충격적..
혹시라도 0이 입력으로 들어올까봐 해당 부분은 따로 예외처리를 했다.
# 백준 11066번: 파일 합치기
이것도 나름 유명한 DP 문제이다.
연속되게 합쳐야 한다는 점에 유의. 즉, 1장과 3장을 먼저 합치면 안된다.
1309.cpp