https://www.acmicpc.net/problem/1034
1034번: 램프
첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져
www.acmicpc.net
풀이
문제를 읽은 직후에 이해가 잘 되지 않았다. 문제 내용은 아래와 같다.
1. 가로 x 세로 크기의 map에 램프가 있다.
2. 각 열의 맨 아래에 해당 열의 램프를 단 번에 키고 끌 수 있는 스위치가 존재한다.
3. 마지막 입력에 스위치를 누를 수 있는 횟수 K가 주어진다.
스위치를 K번 눌러서 각 행의 모든 램프가 켜진 행을 최대한 많이 만들면 된다.
예제 1번을 보면서 문제를 풀어보겠다.
위의 그림은 예제 1번의 초기 상태이다.
스위치를 누를 기회는 총 1번으로 모든 램프가 켜진 행을 최대한 많이 만들려면 두 번째 열의 스위치를 눌러야한다.
두 번째 열을 누르면 위와 같은 상태로 총 2개의 행을 만들 수 있다.
이제 문제가 조금 이해가 되었는가? 그렇다면 모든 램프가 켜진 행을 최대한 많이 구하려면 어떻게 해야할까?
스위치를 눌렀을 때 해당 열의 모든 램프가 변한다.
이걸 생각해보면 모든 전구가 켜진 행은 처음부터 서로 동일한 형태를 가지고 있다. 를 추리할 수 있다.
즉, 동일한 형태의 행이 많을수록 정답일 확률이 높다.
또한, 동일한 형태가 많은 행의 '0' 의 개수가 K번 보다 많다면 모든 램프를 킬 수 없고, '0'의 개수와 K의 수의 홀짝이 같아야한다.
결론은 3가지의 조건을 만족해야한다.
- 동일한 형태의 행이 많은 게 정답일 확률이 높다.
- '0'의 개수가 K번 보다 적어야한다.
- '0'의 개수와 K의 홀짝이 같아야한다.
<최종코드>
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int ans = 0;
N = Integer.parseInt(st.nextToken()); // 행
M = Integer.parseInt(st.nextToken()); // 열
map = new int[N][M];
for (int i=0; i<N; i++) {
String str = br.readLine();
for (int j=0; j<M; j++) {
map[i][j] = str.charAt(j) - '0';
}
}
int K = Integer.parseInt(br.readLine()); // 스위치를 누를 수 횟수
visited = new boolean[N]; // 방문 여부
for (int i=0; i<N; i++) {
if (visited[i]) continue;
visited[i] = true;
// 행마다 0의 개수 구하기
int OffRamp = 0;
for (int num : map[i]) {
if (num == 0) {
OffRamp++;
}
}
// 같은 모양의 행 개수 찾기
int SameRowCnt = find(i);
// K와 0의 개수의 홀짝이 같고, K가 같거나 클 경우
if (K % 2 == OffRamp % 2 && K >= OffRamp) {
ans = Math.max(ans, SameRowCnt);
}
}
System.out.println(ans);
}
public static int find(int row) {
int cnt = 0;
// 같은 행 비교
for (int i=0; i<N; i++) {
if (Arrays.equals(map[i], map[row])) {
visited[i] = true;
cnt++;
}
}
return cnt;
}
}
내가 생각한 시간 복잡도: O(NM)
'알고리즘 > 구현 & 그리디 & 브루트포스' 카테고리의 다른 글
[백준]JAVA - 1913번: 달팽이 (0) | 2022.11.20 |
---|---|
[백준]JAVA - 2503번: 숫자 야구 (0) | 2022.11.15 |
[백준]JAVA - 1202번: 보석 도둑 (0) | 2022.10.21 |
[백준]JAVA - 11399번: ATM (0) | 2022.10.20 |
[백준]JAVA - 1052번: 물병 (0) | 2022.10.08 |