티스토리 뷰
1028번: 다이아몬드 광산
첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다.
www.acmicpc.net
어떤 분이 열심히 백금광에서 백금을 캐고 계시길래 구경해볼겸 백금광에 놀러갔다. 근데 백금광 안에 웬 다이아몬드 광산이 있어서 좀 놀랐다.
아무튼 풀어봤다. 아쉽게도 2트를 했고 40분 정도가 걸렸다.
아이디어는 처음부터 맞은 것 같다. 처음에는 크기 제한을 보고 누적합을 써서 풀어야겠다는 생각이 들었고, 길이를 변수로 누적합을 만들었다. 이를 DP를 활용해서 모든 점에 대한 길이들을 다 담았고, 모든 점에서 길이들이 맞는지 확인하는 방식으로 답을 구했다.
처음 틀린 이유는 예외 처리를 안해서이다. 1이 아예 없는 경우는 0을 출력해야 하는데, 이유는 모르겠지만 1을 출력했다. 그래서 어차피 마지막으로 돌 때 확인 한번씩만 해줘서 추가 반복문 없이 1이 없는 경우를 걸러낼 수 있었다.
두 번째로 틀린 이유는 등호가 이상해서이다. 예외 케이스는 누군가가 게시판에 올려놓은 값인데, 이게 웬만해서는 모든 케이스를 담고 있는것 같아 좋은것 같다.
8 8
11101111
11100111
10111111
11011111
11111111
11110111
11111111
11110110
답은 3이고, 내 코드는 4를 출력했었다. 이유는 4짜리 다이아몬드를 잘 찾아보면 이렇게 돼있다.
0
1 1
1 1
1 1
1 1
1 1
1
이걸 4짜리 다이아몬드가 있다고 답으로 잡아서 틀렸었다. 등호가 어디 잘못 껴있지는 않은지 확인하고 돌려보니 잘 걸러내서 제출해보니 맞았다.
구현하다가 딴짓 안하고 집중했으면 더 빨리 풀고 정확하게 풀었을 것 같아서 좀 아쉽다.
'코딩일지' 카테고리의 다른 글
| 백준 13433 - 기하 문제 (1) | 2023.11.03 |
|---|---|
| 9월 일지 (0) | 2023.09.30 |
| 백준 그리디 일지 (3) (0) | 2023.04.29 |
| 백준 DP 일지 2 (0) | 2023.04.20 |
| 백준 그리디 일지 (2) - 순열 사이클 분할 (0) | 2023.04.05 |