자바칩

난이도: Gold 5문제: https://www.acmicpc.net/problem/15686 N의 크기는 50으로 작다.하지만 N의 크기가 작다고 이중 for문을 돌려버리면 시간 초과가 떠버린다.이중 for문은 시간복잡도가 O(n^2)이니까 50 * 50 = 2500이면 충분하지 않은가? 라고 생각할 수도 있지만 절대 그렇지 않다. 이중 for문을 사용하면 시간 복잡도는 생각보다 어마어마하다.M의 개수는 최대 13개. 즉, dfs로 13번 파고들면 이중 for문을 13번이나 돌려야 한다.즉, for (1~50)     for (1~50)           for (1~50)               for (1~50)                    for (1~50)                  ..

난이도: Gold 4문제: https://www.acmicpc.net/problem/14502  세로: N, 가로: M인 N * M 행렬이 있다.  3개의 벽(1)을 임시로 둔다.  바이러스(2)가 벽(1)을 제외하고 상하좌우로 퍼진다.  바이러스가 퍼지지 않은 구역은 남은 0의 개수를 세어 보면 된다.총 27개가 나온다.  바이러스가 최소한으로만 퍼지게, 즉 안전 영역의 개수가 최대한 많게 3개의 벽을 세워야 한다. N, M의 최대 개수가 8인 것을 보면 시간 복잡도에 전혀 영향을 끼치지 않는다.벽을 3번 세우려면 최소 6중 for문을 돌려야 할 것 같은데,8 * 8 * 8 * 8 * 8 * 8 = 262,144인 것을 보면 정말 시간 복잡도를 신경 쓰지 않아도 된다. 3개의 벽을 세우기 위해서는 브루..

난이도: Silver 1문제: https://www.acmicpc.net/problem/2468   '그 크기가 최대인 영역'처음에는 이게 무슨 말인지 이해가 안 돼서 여러번 읽어봤다. 도대체 어떻게 세어야 저게 5개가 되는거지...? 왼쪽 아래꺼만 세어도 7개인데..? 하면서 답답해 하다가혹시나 나처럼 이해가 안 되는 사람이 있나 해서 질문 게시판을 뒤져 보았다.  고수님들이 답변을 해주신 것을 보고 드디어 이해를 하였다.그리고 문제 텍스트를 작성한 사람을 약간 원망하였다.. 좀 이해되기 쉽게 써주지.. 하면서 ..ㅋㅎㅋㅋ 자 그러면 이제 이해했으니 문제를 풀어나가야겠다!   높이가 4 이하인 모든 지점이 물에 잠긴 경우, 분홍색: 물에 잠기는 지점 파란색: 물에 잠기지 않는 안전한 영역  "인접한 영..