[BOJ/1034] 램

1. 문제

1) 문제 링크

    : https://www.acmicpc.net/problem/1034

1034번: 램프

 

2) 설명

램프의 열을 조작하는 스위치를 K번 조작해서 램프가 모두 켜져 있는 행의 개수를 최대로 만드는 문제

2. 풀이

1) 알고리즘

    : 브루트포스

 

2) 풀이 설명

   2-1) 재귀

    첫 시도는 재귀로 시도했으나 시간초과로 실패했다. 생각해보니 열이 최대 50개인데 50개의 열을 켜고 끄는 경우를 생각하면 2의 50제곱이 되어서 당연히 시간초과가 날 수밖에 없던 것 같다.

    그래서 해당 열까지 모든 램프가 켜진 행의 개수가 이전에 구했던 모든 램프가 켜진 행의 최대 개수보다 작거나 같다면 더 탐색을 진행하지 않는다. (왜냐하면 더 탐색을 해봤자 이전에 구한 최대값을 넘을 수 없기 때문에)

    이렇게 하니까 일단 답은 맞았다.

 

  2-2) 맵 사용

    다른 사람들의 풀이를 참고해보니 초기 램프 배열에서 패턴이 똑같은 행의 개수를 구하는 게 더 편해보였다.

    대신 이때 초기에 한 행에서 꺼져 있는 램프의 개수가 K개 이하여야 하고, 남은 스위치 조작 횟수(K - 꺼진 램프 개수)가 짝수 개여야 한다. 스위치를 조작해야될 횟수가 x번 남았을 때 x가 짝수라면 아무 열이나 껐다 켰다 두 번씩 반복하면 되는데, x가 홀수 번이라면 껐다 켰다를 반복하고나서 마지막에 결국 한 번 더 뒤집어야 하기 때문이다.(결국 램프가 다 켜진 행에서 한 번 더 스위치를 바꾸므로 한 개의 램프가 꺼지게 된다)

 

    그래서 맵(key : 램프 행, value : 개수)을 사용해서 초기 램프 행들 중 같은 패턴을 가지는 행 개수를 카운팅 해줬다.

 

    예를 들어

 

    1 - 1001

    2 - 0100

    3 - 1100

    4 - 1001

 

    이렇게 있다면 맵에는 {1001 : 2, 0100 : 1, 1100 : 1} 이렇게 들어가게 된다. 그리고 이 맵을 돌면서 행에서 꺼진 램프의 개수가 K개 이하이고, 꺼진 램프를 모두 켰을 때 (K - 꺼진 램프의 개수)가 짝수인 경우에 답을 업데이트해나갔다.

 

3. 코드

//재귀 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int N, M, K, answer = -1;
vector<string> lamp(50);

void reverseCol(int colIdx){
	//colIdx 열 램프 뒤집기
	for(int i=0;i<N;i++)
		lamp[i][colIdx] = (lamp[i][colIdx] == '0'? '1' : '0');
}

int countRow(int colIdx){
	//colIdx까지 몇 개의 램프가 켜져있는지 확인
	if(colIdx == 0)
		return 0;
	int i, j, answer = 0;
	for(i=0;i<N;i++){
		for(j=0;j<colIdx;j++){
			if(lamp[i][j] == '0')
				break;
		}
		if(j == colIdx)
			answer++;
	}
	return answer;
}

/*
	재귀 접근
	@colIdx 열 번호
	@changeCount 램프 열을 켜고 끌 수 있는 남은 횟수
*/
void solve(int colIdx, int changeCount){
	if(colIdx == M){
		//마지막 열일 경우
		if((K - changeCount)%2 == 0)
			//램프를 켜고 끌 수 있는 남은 횟수가 짝수일 경우에만 업데이트
			answer = max(answer, countRow(M));
		return;
	}
	
	//앞서 구한 최대로 켤 수 있는 램프 행의 수보다 켜져있는 램프의 수가 적으면 더 돌리지 않음
	if(countRow(colIdx + 1) > answer)
		solve(colIdx + 1, changeCount);

	reverseCol(colIdx);//뒤집기
	if(countRow(colIdx + 1) > answer && changeCount < K)
		//앞서 구한 최대로 켤 수 있는 램프 행의 수보다 켜져있는 램프 행의 수가 적으면 더 돌리지 않음
		solve(colIdx + 1, changeCount + 1);
	reverseCol(colIdx);//다시 뒤집기
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	for(int i=0;i<N;i++)
		cin >> lamp[i];
	cin >> K;
	
	solve(0, 0);

	cout << answer << endl;

	return 0;
}

//패턴과 맵을 이용한 풀이
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, K, answer = 0;
	cin >> N >> M;
	string lamp;
	//램프 행, 개수
	map<string, int> lampMap;

	for(int i=0;i<N;i++){
		cin >> lamp;
		//램프 맵에 카운트 증가
		lampMap[lamp] += 1;
	}
	cin >> K;

	for(auto x : lampMap){
		string row = x.first;
		int val	= x.second;
		//행에 있는 0의 개수
		int zeroCnt = count(row.begin(), row.end(), '0');
		
		//행에 있는 0을 모두 켰을 때 램프 열을 뒤집을 남은 횟수가 짝수여야 함.
		if(zeroCnt <= K && (K - zeroCnt)%2 == 0)
			answer = max(answer, val);
	}

	cout << answer << endl;

	return 0;
}

 

4. 느낀점

- 재귀에서 시간초과난다고 포기하지 않은 나 자신 칭찬한다

- 하지만 아집을 버리고 포기했더라면 더 좋은 방법을 찾을 수도 있었을 텐데 미한한 나 자신 혼낸다

- 사실 스트링 패턴으로 접근하는 풀이는 나 혼자서는 오래 고민한다 해도 생각해내기 힘들었을 것 같다. 좀 더 열린, 다른 시각으로 접근하는 연습을 해보도록 하자