[CodeForces] 706C - Hard problem

이번학기 듣는 알고리즘 연습 수업 과제로 나온 문제인데, 이틀째 골머리를 앓다가 푼 게 너무 기뻐서 기록하기로 했다.

교수님도 그렇게 말하셨고, 나도 푸는 아이디어 자체는 어렵지 않다고 생각한다.(다른 문제들에 비해)

근데 코드 작성하는 게 좀 빡친다.

문제

문자열을 뒤집을지 말지를 결정하는데, 뒤집게 되면 cost가 발생한다.
주어진 문자열들을 최대한 적은 cost로 사전식 배열로 구성되게 하는 문제.
불가능하다면 -1을 출력한다.

풀이

706C 문제 해결하는데 어디서 논리적 오류가 발생하는지 고민해봐도 잘 모르겠어서 질문 남김니다.

비교하는 이전 문자열 s1, s1을 뒤집은 문자열 r1
현재 문자열 s2, s2를 뒤집은 문자열 s2로 주요 변수 구성하였고

사전식 순서를 만족하는지를 각각 비교하여 comp1,2,3,4에 저장하였습니다.

original, reverse 둘 다 만족하는 경우 -> 둘 중 작은 값에 + cost
하나만 만족하는 경우 -> 만족하는 경우에 해당하는 값
둘 다 만족하지 않는 경우 -> maxNum(long long 의 최댓값)

이렇게 하면 min에서 이전 케이스가 안되는 경우를 자동으로 걸러주고,
반복문 마지막에서 cost와 costReverse가 모두 maxNum이면 종료시켜 -1을 출력하도록 했습니다.

codeforce 테스트케이스 8번에서 실패합니다. (기댓값이 9만...

교수님한테 질문하려고 메모장에 끄적여둔 거 재탕

n=44000, 인 테스트 케이스에서 기댓값이 9XXXX인데 -1이 출력됐다.
테스트케이스가 저모양이라 돌려보지도 못 하고 계속 앓았다... 하

그리고 강의를 돌려보다가 코드가 다른 점을 찾았다.
비교 과정에서 둘이 같은 경우에 대한 생각을 안 했었다.
comp3 = (strcmp(r2.c_str(),s1.c_str()) >= 0) 등호를 >에서 >=으로 바꿔줬다.
사실 처음엔 strcmp에 전달하는 변수 순서를 다르게
(strcmp(s1.c_str(),r2.c_str()) < 0) 이런 식으로 했었는데 뭐 결국 문자열이 같은 경우에 대해서 정확히 처리를 못 했기 때문인 걸로 생각하기로 했다.

코드

#include<iostream>
#include<string>
#include<algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
int main(){
	
	freopen("input.txt", "r", stdin);
	int n;
	const long long maxNum = LLONG_MAX;
	long long cost, costReverse, tmp1;
	bool comp1, comp2, comp3, comp4;
	cin>>n;
	long long costs[n];
	string s1, s2, r1, r2;
	
	for(int i=0; i<n; i++){
		cin>> cost;
		costs[i] = cost;
	}
	
	cin>>s1;
	r1 = s1; reverse(r1.begin(), r1.end());
	cost = 0; costReverse = costs[0];
	int i;
	for(i=1; i<n; i++){
		cin>>s2;
		r2 = s2; reverse(r2.begin(), r2.end());
		tmp1 = cost;
		
		comp1 = strcmp(s2.c_str(), s1.c_str()) >= 0 ;
        comp2 = strcmp(s2.c_str(), r1.c_str()) >= 0 ;
        
		if(comp1&&comp2){
			cost = min(cost, costReverse);
		}
		else if(comp1){
			cost = cost;
		}
		else if(comp2){
			cost = costReverse;
		}
		else cost = maxNum; 
		
		comp3 = (strcmp(r2.c_str(),s1.c_str()) >= 0) &&tmp1!=maxNum;
        comp4 = (strcmp(r2.c_str(),r1.c_str()) >= 0) &&costReverse!=maxNum;
        if(comp3&&comp4){
			costReverse = min(tmp1, costReverse) + costs[i];
		}
		else if(comp3){
			costReverse = tmp1+costs[i];
		}
		else if(comp4){
			costReverse = costReverse+costs[i];
		}
		else costReverse = maxNum; 
		
		if(cost==maxNum && costReverse ==maxNum) break;
		s1=s2; r1=r2;
	}
	if(i==n) cout<<min(cost,costReverse);
	else cout<<-1;
	return 0;
}

편안해졌다.