아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

조건문 줄이기

시간 제한1초메모리 제한128 MB

요약
단일 변수 조건으로 번호가 있는 전등을 켜는 if문들에서 모든 입력에 대한 동작을 유지하면서 삭제할 수 있는 최대 줄 수를 구합니다.
난이도

보통10점 중 7점

유형
구간, 해시맵, 그리디
정답자
아직 제출이 없습니다

문제

본졸은 회사에서 새 일을 맡았다. 조명 여러 개를 제어하는 파스칼 코드를 받았고, 프로그램의 동작을 원래와 완전히 똑같이 유지하면서 코드 길이를 최대한 줄여야 한다. 코드는 조건문으로만 이루어져 있고, 각 줄은 다음 형태다.

if <변수> <비교 연산자> <비교 값> then turnOn( <조명 번호> );
  • <변수>는 길이가 255 이하인 소문자 알파벳 문자열이고, 파스칼 정수 변수의 이름이다.
  • <비교 연산자>는 <, >, = 중 하나다.
  • <비교 값>은 변수와 비교할 32비트 정수 상수다.
  • <조명 번호>는 조건 <변수> <비교 연산자> <비교 값>이 참일 때 켜야 하는 조명의 번호이고, 역시 32비트 정수 상수다. 이미 켜져 있는 조명을 다시 켜면 아무 일도 일어나지 않는다.

변수에는 어떤 정수든 들어갈 수 있다. 두 프로그램의 동작이 완전히 같다는 것은, 변수에 어떤 정수를 넣더라도 켜지는 조명의 집합이 서로 같다는 뜻이다.

본졸이 할 수 있는 수정은 한 줄을 통째로 지우는 것뿐이다. 원래 프로그램과 동작이 완전히 같도록 유지하면서 최대한 많은 줄을 지우려고 한다. 지울 수 있는 줄 수의 최댓값을 구하라.

입력

입력은 테스트 케이스 여러 개로 이루어진다. 테스트 케이스의 첫 줄에는 코드의 줄 수 nn (1≤n≤5001 \le n \le 500)이 주어진다. 이어지는 nn개 줄에 조건문이 한 줄에 하나씩 주어진다. 각 조건문에서 if 뒤, <변수> 뒤, <비교 연산자> 뒤, <비교 값> 뒤, then 뒤, turnOn( 뒤, <조명 번호> 뒤에는 공백이 정확히 하나씩 있다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 테스트 케이스가 아니다.

출력

테스트 케이스마다 본졸이 지울 수 있는 줄 수의 최댓값을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    7
    if aa < 4 then turnOn( 3 );
    if aa > 7 then turnOn( 3 );
    if aa = 7 then turnOn( 3 );
    if aa = -1 then turnOn( 3 );
    if aa < 7 then turnOn( 3 );
    if b = 6 then turnOn( 4 );
    if b = 6 then turnOn( 3 );
    4
    if pq = 6 then turnOn( 7 );
    if pq = 6 then turnOn( 7 );
    if pq = 6 then turnOn( 1 );
    if pq = 2 then turnOn( 1 );
    4
    if pq = 6 then turnOn( 8 );
    if pq = 6 then turnOn( 8 );
    if pq = 6 then turnOn( 9 );
    if pq < 8 then turnOn( 9 );
    0
    
    예상 출력
    3
    1
    2