오늘의 목표
어제 헬스 3시간을 끝내고 집에오니 오랜만에 체력이 남아서 요리부터 계획까지 모든 걸 끝냈음!
앞으로도 꾸준히 헬스로 근력키우고 건강해져서 SSAFY 방학때 국토종주를 하는 것이 내 목표다!
그걸 이루기 위해 오늘 싸월급 받아서 헬스 3개월권 끊으러 갈거임 히히
그 전에 열심히 공부하장~~
1. PS 2문제이상 풀기
오늘도 기출문제 모음에서 풀어볼 생각이다.
산 모양 타일링
윗변이 N이고 아랫변이 N+1의 길이인 사다리꼴을 정의하고, 윗변에 삼각타일을 추가한다면 전체 영역을 채우는 경우의 수는 몇개인지 출력하는 문제이다.
sol 1)
우선 규칙성부터 찾기 위해 하나하나 그려봤다
n=1; 삼각타일 하나에서 시작해서
n=2; n이 1일 때에 하나를 붙이고 새로운 모양인 평행사변형을 가져오고
n=3; n이 2일 때에 하나를 붙이고 앞과 뒤에 붙이는 방식으로 추가하고
n=4; n이 3일 때에 하나를 붙이고 앞과 뒤를 붙이려다 중복이 있음을 발견하고 또 새로운 모양인 평행사변형 2개 붙인 모양을 만든다
...
이렇게 찾아서는 규칙이 보이지가 않음
그래서 좀 더 생각하다가
2개 전 단계에서 평행사변형을 붙이고, 1개 전 단계에서 삼각타일을 붙인다고 생각하면 새로운 모양에 대한 대처가 가능했다.
단, 무조건 뒤에 붙인다는 조건을 추가해야 계산이 깔끔해짐.
그러면 결국 n-1번째 타일 모양에 삼각형 타일 한개 붙인 케이스와 n-2번째 타일 모양에 평행사변형 모양 타일을 하나 더 붙인 케이스가 n번째 개수이므로
dp[n] = dp[n-1] + dp[n-2]임을 확인할 수 있다.
하지만, 문제는 여기서 끝이 아니라 tops[i]까지 고려해줘야 한다는 점이다.
사다리꼴 위에 솟은 삼각타일까지 채우기 위한 경우는 가장 위를 삼각타일로 채우거나 서있는 평행사변형 타일을 채우는 것이다.
즉, 기존에 구해둔 dp 배열을 활용하여 점화식을 만들 수 있다.
이제 기존 dp를 활용하여 dp_final을 만들어야하는데 중간에 코드가 꼬인건지 자꾸 Exception이 떴다..
이대로 답 코드를 보기엔 너무 아까워서 좀 더 고민하고 짜봐야겠음
드디어 풀었는데 너무 아쉬운 실수로 가득했다..
1) nullpointException
tops 배열의 인덱스가 n개인데 전체 (2 x n + 1)로 돌려서 당연히 오버
2) 위 삼각형이 추가될 때 연산 실수
이 그림을 다시 보면 dp[1]과 dp[2]를 더해야하는데
dp_final 배열 기준으로보면
dp_final[n] = (dp_final[i-1]) + (dp_final[i-1] +dp_final[i-2]) = 2 * dp_final[i-1] + dp_final[i-2]]
로 식을 구해야하는데 dp를 자꾸 써서 계산에 오류가 발생했음
사실상 dp_final만으로 계산이 가능했던 문제
이 간단한 dp를 문제 첫인상때문에 2시간이나 걸렸다는 점이 아쉬웠음
TMI) 새로운 장비 등장!
히히
다얼유 A104PRO FLEX 키보드 드디어 주문해서 SSAFY에 가져왔다!
저소음 머스타드 축으로 샀는데 키가 가벼워서 누르는데 힘이 거의 들지 않고, 저소음이라 도각도각 소리에 너무 만족스러움!
색도 너무 예쁘다~
키보드 디스플레이도 너무 뽀짝하고, 덕분에 타이핑이 즐거움
아 너무 신나 😎
