반응형
p21771 가희야 거기서 자는 거 아니야
처음 접근방법은 G의 각 꼭짓점 별로 좌표를 추적해서 좌우에 P가 있는지 탐색해보는 방식으로 접근했었는데, 정확한 이유는 모르겠지만 실패했다.
그래서 생각해 본 방법이 P의 넓이를 구하고 P의 갯수를 카운트했을 때 넓이가 안맞으면 가희가 베개를 사용하고 있는 것으로 판단하기로 해보고 문제를 풀어봤다.
hint
----
P의 갯수를 활용하는 것이 핵심
----
Solution
실행시간 - 124ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | import java.util.*; import java.io.*; class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int r = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); st = new StringTokenizer(br.readLine()); int gr = Integer.parseInt(st.nextToken()); int gc = Integer.parseInt(st.nextToken()); int pr = Integer.parseInt(st.nextToken()); int pc = Integer.parseInt(st.nextToken()); char[][] map = new char[r][c]; for(int i = 0; i < r; i++){ map[i] = br.readLine().toCharArray(); } int n = pr * pc; // 60 int count = 0; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ if(map[i][j] == 'P'){ count++; } } } if(count == n){ System.out.println(0); }else{ System.out.println(1); } } } | cs |
다음에 기회가 된다면 각 꼭짓점 별로 판단하는 방식을 채용해보고 싶다... 정말 최고의 최적화일거같은데 반례가 어느걸까 궁금하다
반응형
'공부 > Algorithm' 카테고리의 다른 글
| 알고리즘 근황 (0) | 2023.07.23 |
|---|---|
| 백준 11822번 Document 자바로 풀어 본 짧은 글 (0) | 2023.06.08 |
| 백준 13717 포켓몬Go 자바로 풀어 본 짧은 글 (0) | 2023.05.25 |
| 백준 1418 K-세준수 자바로 풀어 본 짧은 글 (0) | 2023.05.24 |
| 백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글 (0) | 2023.04.30 |