PKU 1298. The Hardest Problem Ever. [판정:AC]

인증

포스트를 수정하다보니 결과에는 이상이 없지만 알고리즘은 잘못된부분이 있어서 그 부분을 수정하고 제출했는데

pku 서버가 맛이 갔는지 어쩐지 지금 Waiting하는 사람들만 2page를 채우는듯 -_-;

소스

#include <stdio.h> #include <string.h> #include <ctype.h> int compare( char *src, char *des ) { int i; for( i = 0; des[i] != '\0'; i++ ) { if( src[i] != des[i] ) return 0; } if( strlen(src) == strlen(des) ) { return 1; } else return 0; } void main() { char str[201]; int progress = 0; while( gets(str) ) { int i; int sum = 0; int limit; if( compare( str, "ENDOFINPUT" ) ) break; if( compare( str, "START" ) ) progress = 1; while( progress ) { gets(str); if( compare( str, "END" ) ) { progress = 0; break; } sum += strlen(str); if( sum > 200 ) limit = 200 - (sum - strlen(str)); else limit = strlen(str); for( i = 0; i < limit; i++ ) { if( isalpha(str[i]) ) { printf("%c", (str[i] - 'A' + 21)%26 + 'A'); } else { printf("%c", str[i]); } } printf("\n"); } } }

만들 때는 몰랐던건데,

Dlbo군 풀이를 보니 strcmp라는 함수가 이미 built-in이었군요 -_-;

몇번 본적은 있는데 평소에 안쓰다보니 완전 잊고 살았던 1人

우선, main함수 위의 compare는 아마 strcmp와 동일한 기능을 하지 않을까 싶습니다

strcmp가 있다는걸 완전 잊어서 모른다고 할 수 있을 정도의 상태라서 직접 만들었습니다

main함수를 보시면

str는 input의 한 행이 최대 200자라고 되어있어서 NULL문자를 포함할 것을 고려해 201개로 선언한 것이고,

progress는 input의 길이를 고려해서 약간의 예외를 처리하기 위한 key입니다

일단 처음에 문자열의 입력을 받고

그게 ENDOFINPUT이 아니면서 START이면 progress에 참값(1)을 부여합니다

그리고 progress값이 참일 때에 한해서 내부 while문을 돌게 되는데,

암호문에 해당하는 부분을 입력받고 그것이 END라면 progress에 거짓값(0)을 부여하고  그것이 END가 아니면 출력을 하면 됩니다

이때, 개인적으로 처리한 예외가 하나 있는데,

input의 길이가 200자를 넘어갈 경우 또는 200자를 넘어가지 않고 문자열의 중간에 개행문자가 끼어있는 경우

(즉, 후자의 경우가 뜻하는 것은 START와 END 사이에 암호문이 2줄 이상 나열된 경우입니다)

-에 대해서 처리를 하기 위해 sum과 limit라는 변수가 존재합니다

우선 sum은 현재 처리한 문자의 개수가 START 이후로(& END 전까지) 몇개나 되는지 계산하는 변수이고,

limit는 sum의 상태에 따라 input의 출력 길이를 제한하는 변수입니다

예를 들어,

170자를 처리한 상태에서 20자의 추가입력이 들어오면 계속 처리하고,

190자를 처리한 상태에서 30자의 추가입력이 들어오면 처음 10자만 처리하도록 limit를 조절해줍니다

그렇게 limit가 설정되면 for문을 돌면서 출력을 시작하는데,

암호문(알파벳)이면 평문으로 출력하고, 그 외의 것들은 그대로 두라고 했으니 해당 문자가 알파벳인가를 판별할 수 있는 함수가 있으면 편할 듯 합니다

그런데 실제로 ctype.h에 isalpha()가 있지요 ㅋㅋ 써줍니다

그럼 이제 임의의 알파벳에 대해 평문으로 바꾸는 작업이 필요한데, 다음과 같은 몇가지 변환(실은 함수)이 필요합니다

{A, B, …, Z} → {0, 1, …, 25}에 해당하는 변환 1가지, … ①

{0, 1, …, 25} → {0, 1, …, 25}에 해당하는 변환 1가지, … ②

{0, 1, …, 25} → {A, B, …, Z}에 해당하는 변환 1가지 … ③

① {A, B, …, Z} → {0, 1, …, 25}

C언어를 처음 배우게 되면 char형의 아스키코드값을 한번쯤 보게 되는데, 이것을 잘 보면

소문자는 소문자끼리, 대문자는 대문자끼리 26자가 연속한 아스키코드값을 가지고 있습니다

즉, {A, B, …, Z} 안의 원소 중 가장 작은 값을 가지고 있는 문자가 A이므로

임의의 x ∈ {A, B, …, Z} 에 대해 {x-A}라는 집합을 생각하게 되면 이것이 곧 {0, 1, …, 25}가 됩니다

② {0, 1, …, 25} → {0, 1, …, 25}

이제 문제에서 주어진 변환방식대로 암호문을 평문으로 바꾸어야 하는데,

{A, B, …, E}를 제외하고 보면 다들 -5 연산으로 평문화 할 수 있습니다

그래서 일단 -5 연산을 수행하고 나면 {0, 1, …, 25} → {-5, -4, …, 20} 이 되는데,

현재 A와 대응되는 값이 0이므로 음수에 대해서는 적당한 조치를 취해야 합니다

그것이 바로 나머지연산이죠 :)

A부터 Z까지 26자이므로 26에 대한 나머지를 구하면 {-5, -4, …, 20} → {0, 1, …, 25} 가 가능하게 됩니다

-만,

프로그래밍 언어에서는 나머지가 양수라는 사실이 보장되지 않더군요 -_-;

따라서, 임의의 x ∈ {0, 1, …, 25} 에 대해 {(x + 21) mod 26}이라는 집합을 생각하게 되면 {0, 1, …, 25}가 됩니다

(왜 x-5에 +26을 하였는지는 생각해보세요 :D)

③ {0, 1, …, 25} → {A, B, …, Z}

이제 마지막으로 이것을 알파벳으로 바꾸어주면 평문이 되는데,

A와 대응되는 값이 0이었으므로

임의의 x ∈ {0, 1, …, 25} 에 대해 {x+A}라는 집합을 생각하게 되면 이것이 {A, B, …, Z}가 됩니다

설명 끝!

졸면서 글쓰려니 여간 힘든게 아니군요 =_=