ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2529.부등호
    알고리즘/백준 BAEK JOON 2020. 5. 18. 01:20

    (*)이번에 풀어볼 문제는 백준의 2529번 부등호이다. 꽤 오랜시간이 걸린 문제이다..ㅠㅠ

    역시나 풀이 전 침착하게 분석으로 규칙을 찾아야한다..

    분석을 조지거나 안하고 구현을 시작하면 예외처리를 빼먹을 시, 다시 구현해도 시작이 부족할 것이다..

    -> 조짐의 지름길..

     

    2529번: 부등호

    두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제��

    www.acmicpc.net

    문제의 내용은 간단하다. k개의 부등호를 입력받아 부등호에 맞게

     0~9까지의 숫자로 만들 수 있는 최소값과 최대값을 구하는 것이다.

    생각보다문제가 어려웠다.. 규칙을 발견했는데 조금 침착하게 구현할 필요가 있을 것 같다.

     

    * 문제를 푸는 포인트는 다음과 같다.

    최대값이나 최소값이 가장크고 가장작은 것을 이용한 비교, 그리디를 사용하자

    최대값일 경우에는 시작값은 9일 것이고  '>'를 만나기 전까지는 값이 순차적으로 커진다. 

    예를 들어 부등호가 < < > < 이면 '>'를 만나기전까지는 수는 그대로 증가하며 '<' 의 수만큼의 시작값에서 뺀 숫자부터 증가한다.

    즉, 9 - 2 ( '<'의 갯수 ) = 7부터 증가한다. 그러므로 7 < 8 < 9 > 가 된다.

    그 다음부터는 최대 시작값이 9가 아닌 9 - 2 ( '<'의 갯수 ) - 1 ( 7은 사용함 ) = 6으로 다시 위의 과정을 진행하면 된다.

    그리고 위의 과정 이후에 '>' 가 더 이상 나오지 않아 숫자는 남았는데 출력을 못하는 경우가 있기 때문에 한 번 더 진행한다.

     

    < Code 설명 >

    #include <iostream>
    
    using namespace std;
    
    char bu[10];
    
    int main() {
    	int k;
    	cin >> k;
    	for (int i = 0; i < k; i++)
    		cin >> bu[i];
    
    	int n = 0;
    	int ans = 9;  // 시작 최대값
    	for (int i = 0; i < k; i++){
    		if (bu[i] == '>'){ // '>'전까지 else에서 n을 증감
           		//n을 뺀곳부터 시작값까지 출력
    			for (int j = ans - n; j <= ans; j++) 
    				cout << j;  
    			ans = ans - n - 1; // 출력 후 최대 시작값 조정
    			n = 0;             // 카운트할 값 초기화
    		}
    		else
    			n++;  // '>'가 아닐 경우 증감
    	}
        
    // 숫자는 남았는데 '>' 부등호가 없어서 출력 과정이 진행이 안되므로 아래와 같이 진행하여 나머지 출력 
    	for (int j = ans - n; j <= ans; j++) 
    		cout << j;
    	cout << "\n";
    
    
    	ans = 0; 	// 최소값을 위한 초기화
    	n = 0;      // 최소값을 위한 초기화
        
    	for (int i = 0; i < k; i++){
    		if (bu[i] == '<'){ // 위와 같지만 최소이므로 부등호를 반대로 한다.
    			for (int j = ans - n; j <= ans; j++)
    				cout << -1*j; 
                    // 출력 값이 -1을 곱해주면 최소값 그대로 유지가능하다.
                    
    			ans = ans - n - 1;
    			n = 0;
    		}
    		else
    			n++;
    	}
        
    // 숫자는 남았는데 '>' 부등호가 없어서 출력 과정이 진행이 안되므로 아래와 같이 진행하여 나머지 출력 
    	for (int j = ans - n; j <= ans; j++)
    		cout << -1*j;
    	cout << "\n";
    	return 0;
    }

     

     

    * 참고

    -> 최소값의 경우 위와같이 하기 싫다면 for문을 반대로 구현하면 된다.

    {
        ans = 0;
    	n = 0;
    	for (int i = 0; i < k; i++){
    		if (bu[i] == '<'){
    			for (int j = ans + n; j >= ans; j--)
    				cout << j;
    			ans = ans + n + 1;
    			n = 0;
    		}
    		else
    			n++;
    	}
    	for (int j = ans + n; j >= ans; j--)
    		cout << j;
    	cout << "\n";
    }

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    15649 ~ 15652.N과 M(1~4)  (0) 2020.05.20
    1541.잃어버린 괄호  (2) 2020.05.18
    2529.부등호  (0) 2020.05.18
    1138.한 줄로 서기  (0) 2020.05.17
    1120.문자열  (0) 2020.05.17
    1018.체스판 다시 칠하기  (0) 2020.05.04

    댓글 0

Designed by Tistory.