[C++] 백준 1034번: 램프

🔗 문제

1034번: 램프

1034번: 램프

 

✏️ 풀이

불을 하나 켤 때마다 모든 열을 돌면서 켜야 할 생각에 아주아주 막막했다.

발상을 못 해내서 도움을 받았다...

그래서 이해하기 위해서 풀이를 쓴다!!!!!

 

 

---

✔️ 단계1

정답은 열에 있지 않고, 행이다. 행에 위치한 램프가 모두 켜졌는지 (행 완성) 아닌지가 정답을 좌우한다.

만약에 여러 행이 주어졌을 때 중복되는 행이 있다고 생각해보자.

어딜 켜든 똑같이 생긴 행들은 함께 상태가 바뀐다.

만약 똑같이 생긴 행1,2,3 중에 1이 다 켜진 상태면? 2, 3도 켜진 상태다. 똑같이 생긴 애들을 다시 확인할 필요가 없다.

그래서 똑같이 생긴 행들의 최대개수를 세어주는 작업이 필요하다. 

 

 

[필요한 로직]

이 작업은 그냥 뚝딱 map한테 맡겨버리자.

if(map.find(input) != map.end())
{
	++map[input]; // incr
}
else
{
	map[input] = 1; // add
}

 

✔️ 단계 2

누를 수 있는 횟수가 정해져있다. K번을 눌러서 행이 완성되지 않을 수도 있다는 말이다.

우리는 행만 바라보기로 했으니까 행을 들여다 보자.

01010101 -> 4번 눌러야 한다.
11111 -> 안 눌러도 된다.
00000 -> 5번 눌러야 한다.
1001 -> 2번 눌러야 한다.
1011 -> 1번 눌러야 한다. 

→ 행이 가진 zero의 개수가 행완성을 결정 짓는군.. !

 

 

이걸 우리가 주어진 K 와 엮어보자.

 

만약 K가 2라면?

01010101 -> 4번 눌러야 하지만 횟수가 모자라다.
11111 -> 누르는 순간 망가진다...?? 아니다. 같은 곳을 여러번 눌러서 toggle 시키면 된다. 
00000 -> 5번 눌러야 하는데 모자라다.
1001 -> 2번 눌러야 한다-> 만족
1011 -> 같은 곳을 2번 눌러서 만족가능하다.

이렇게 같은 곳을 여러번 눌러서 만족 시킬 수 있다.

 

여기서 k의 개수가 zero 이상이어야 하는 조건을 가진다는 걸 알 수 있다.

if(k >= zero) 

 

 

K가 3이라면?

01010101 -> X
11111 -> X
00000 -> X
1001 -> X
1011 -> X

2로 딱 떨어질 때랑은 다른 결과가 된다!! zero %2 == k%2 이어야지 toggle할 수 있는 상태다.

 

 

[행 완성 조건]

if(k>=zero && k%2 == zero%2)

단계1, 단계2를 합치면 시간초과 없이 문제를 풀 수 있다.

 

 

 

시간 복잡도

• 입력 : N*M
• 풀이 : N*M + N
  • 모든 행에 대한 N에대해서
    • M번 돌며 zero 카운팅
  • 저장된 모든 map을 돌며 최대값 구하기
    • 최악의 경우 N번

총 : NM + NM + N

 

 

 

💾  소스

#include <iostream>
#include <string>
#include <map>

const int MAX = 50 + 1;

int main()
{
    int N, M, K, answer = 0;
    std::string input[MAX];
    std::map<std::string, int> map;
    
    //input
    std::cin >> N >> M;
    for(int i=0; i<N; ++i)
        std::cin >> input[i];
    std::cin >> K;
    
    //solve
    for(int i=0; i<N;++i)
    {
        if(map.find(input[i]) != map.end())
        {
            ++map[input[i]];
        }
        else
        {
            int zero = 0;
            for(int j=0; j<M; ++j)
            {
                if(input[i][j] == '0')
                    ++zero;
            }
            
            if((zero<=K) && (zero%2 == K%2))
            {
                map[input[i]] = 1;
            }
        }
    }
    
    for(const auto& [key, value] : map)
    {
        answer = (answer > value ? answer : value);
    }
    
    //output
    std::cout << answer;
    return 0;
}