[백준] 16235 나무 재테크
https://www.acmicpc.net/problem/16235
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든
www.acmicpc.net
나무들의 정보를 담을때 LinkedList, ArrayList 모두 시간초과가 나서 Deque를 사용해서 통과했고, Deque도 하나만 써야 했습니다.
죽은나무를 처리할때 LinkedList, ArrayList, Stack Deque 같은 자료구조 쓰지말고 int[][]로 좌표값만 설정해서 통과됐습니다.
자료구조가 까다로운 문제였습니다.
처음엔 나무들의 정보를 담는 자료구조와 죽은나무 처리할때 쓸 자료구조를 두가지 설정했던게 오류였던것 같습니다.
나무들의 정보와 죽은나무 처리용으로 LinkedList, ArrayList, Stack, Deque로 돌려가며 사용해도 통과가 안됐는데,
죽은나무 처리용 자료구조를 int[][]배열로 바꿔서 구현하고, 나무 정보를 Deque로 처리하니까 통과가 됐습니다.
LinkedList, ArrayList, Stack, Deque 각각이 시간복잡도가 다르고 각각의 연산마다 소요시간이 다르다고 합니다. 그레서 알고리즘에서 사용되는 기능들을 잘 생각해서 알맞은 자료구조를 사용해야 할 것 같습니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 17779 게리 맨더링 2 (2) | 2020.02.22 |
|---|---|
| [백준] 16234 인구 이동 (0) | 2020.02.18 |
| [백준] 17837 새로운 게임 2 (0) | 2020.02.15 |
| [백준] 15684 사다리 조작(Brute force) (0) | 2020.02.14 |
| [백준] 9465 스티커 (Dynamic Programming) (0) | 2020.02.07 |