16918 봄버맨 - solved

알고리즘

• 구현

접근방식

• 시간에 따른 상태 변화를 단계별로 시뮬레이션
  • 1초: 아무것도 하지 않음
  • 2초: 빈 칸에 폭탄 설치
  • 3초: 3초 전에 설치된 폭탄들이 폭발
• 이후 2초와 3초를 반복하며 N초까지 진행
• 각 폭탄의 설치 시간을 기록하여 폭발 시점 관리

시공간 복잡도

• 시간복잡도: O(N × R × C) // N초 동안 R×C 격자를 처리
• 공간복잡도: O(R × C) // 격자 상태를 저장하는 2차원 배열

2138 전구와 스위치 - solved

알고리즘

• 그리디

접근방식

• 스위치를 누르면 해당 위치와 인접한 전구들의 상태가 바뀌는 특성을 이용
  • 첫 번째 스위치를 누르는 경우와 누르지 않는 경우로 나누어 탐색
  • 왼쪽부터 순서대로 처리하며, 이전 전구가 목표 상태와 다르면 현재 스위치를 누름
• 두 가지 경우 중 최솟값을 선택하여 답 도출

시공간 복잡도

• 시간복잡도: O(N) // 리스트 두 번 순회 (첫 번째 스위치를 누르는 경우/안 누르는 경우)
• 공간복잡도: O(N) // 전구 상태를 저장하는 배열