[BOJ] 극장 좌석

[sangholee235]

문제 링크 https://www.acmicpc.net/problem/2302

풀이 사항 풀이 일자: 2024.00.00 풀이 시간: 00분 00초 채점 결과: 오답/시간 초과/런타임 에러/정답 예상 문제 유형: 구현/BFS/DFS/DP/자료구조/문자열 등 시간: 00 ms 메모리: 00 kb

풀이 방법 (풀이 접근 및 방법에 대한 설명 문제를 풀지 못했다면 어느 곳에서 어려움을 느꼈는지 적어주세요!!)

[sangholee235]

문제링크

292

풀이 사항

• 풀이 일자 : 241001
• 풀이 시간 : 30분
• 채점 결과 : 정답
• 예상 문제 유형 : 동적 계획법
• 시간 : 96ms
• 메모리 : 14,032 kb

  풀이 방법

  1. 현재 자리와 내 전자리가 vip인지 고려
  2. 둘 중하나가 vip면 바꿀수없으므로 그전 dp값을 그대로 이어 받음
  3. 바꿀수 있다면 점화식인 dp[i] = dp[i-1] + dp[i-2] 넣기

어려웠던점

dp 시작점을 0으로 하는지 1로 하는지 명확히 안하고 시작해서 좀 걸렸습니다.

[kro46]

문제링크

295

풀이 사항

풀이 일자 : 241001 풀이 시간 : 2시간 채점 결과 : 정답 예상 문제 유형 : 동적 계획법 -> 피보나치 수열 시간 : 100ms 메모리 : 14,292kb

풀이 방법

VIP = 고정석 -> 바뀔 수 없는 좌석 나머지 = 자신의 왼쪽 오른쪽과 자리 변경 가능 ex) 1 12 21 123 213 132 1234 2134 1324 1243 2143 12345 21345 13245 12435 12354 21435 21354 13254
위의 가짓수를 보고 피보나치가 떠오름 이제 구간의 개수와 각 구간별 좌석 수를 구해야함 고정석 전까지 좌석의 개수를 세어 구간을 나누고 구간별 원소의 개수를 eCnt에 저장 모든 구간별 원소의 개수를 구하면 mul에 fibo[]안에 각 원소의 개수를 넣어 곱함 모든 계산이 끝나면 mul 값 출력(총 가짓수는 20억을 넘지 않음-> int사용가능)

어려웠던점

N과 M의 개수에 따라 분기를 나눠줘야하는데 M이 0일 때와 N이 1일때의 경우를 처리해주지 않아서 계속 런타임 에러가 뜨다가 2시간만에 잡음 -> 문제 자체는 어렵지 않았는데 예외처리에 신경을 많이 써야해서 오래 걸렸던 문제임