굳건하게

안녕하세요.

여행벌입니다.

오늘은 백준 16360번 Go Latin 문제풀이를 해보려고 합니다.

ACM-ICPC 2018 본선 문제로 ACM-ICPC 문제 치고는 되게 쉬웠던 것 같습니다.

https://www.acmicpc.net/problem/16360

문제는 'n개의 단어가 주어졌을 때,  pseudo-latin 단어로 바꿔서 출력해주는 알고리즘을 구현하라.' 입니다.

단어의 끝 문자가 위의 테이블에 해당되면, pseudo-latin 문자로 바꿔서 출력해주면 되는데요.

다른 더 좋은 알고리즘이 있을 수도 있지만, 저는 간단한 문제라 더 생각 안 하고 if 문을 통해

간단하게 알고리즘 구현할 수 있었습니다.

[알고리즘설계]

1. switch 문을 통해 입력받은 string의 끝 문자 들을 다 체크한다. 이때, Pseudo-Latin으로 바꿔줘야 하는 문자가 있다면, 바꿔주면서 출력한다. 다만 -n, -ne를 제외하고 모두 원래의 단어에 글자를 추가해주면 되므로 원래의 string을 출력하고 뒤에 추가로 char을 출력해준다.

#include<stdio.h>
#include<string.h>

int main(void) {
	int total_number;
	scanf("%d", &total_number);
	while (total_number > 0) {
		char list1[31];
		scanf("%s", list1);
		switch (list1[strlen(list1) - 1]) {
		case 'a':
			printf("%ss\n", list1); break;
		case 'i':
			printf("%sos\n", list1); break;
		case 'y':
			list1[strlen(list1) - 1] = '\0';
			printf("%sios\n", list1); break;
		case 'l':
			printf("%ses\n", list1); break;
		case 'n':
			list1[strlen(list1) - 1] = '\0';
			printf("%sanes\n", list1); break;
		case 'e':
			if (list1[strlen(list1) - 2] == 'n') {
				list1[strlen(list1) - 1] = '\0';
				list1[strlen(list1) - 1] = '\0';
				//조심! 위에서 마지막 글자를 이미 날려서, strlen이 하나 줄었음!
				printf("%sanes\n", list1);
			}
			else
				printf("%sus\n", list1);
			break;
		case 'o':
			printf("%ss\n", list1); break;
		case 'r':
			printf("%ses\n", list1); break;
		case 't':
			printf("%sas\n", list1); break;
		case 'u':
			printf("%ss\n", list1); break;
		case 'v':
			printf("%ses\n", list1); break;
		case 'w':
			printf("%sas\n", list1); break;
		default:
			printf("%sus\n", list1); break;
		}
		total_number--;
	}
}

너무 간단한 문제라 여기서 해설 마치겠습니다.

안녕하세요

여행벌입니다.

오늘은 백준 14954번 ACM 2017 본선 D번 문제 풀이를 해보겠습니다.

https://www.acmicpc.net/problem/14954

문제는 '어떤 숫자가 주어졌을 때, HappyNumber인지 아닌지 구분해주는 알고리즘을 구현하라.' 입니다.

이 때, HappyNumber 란 숫자가 주어졌을 때, 각 자릿수의 제곱을 더해나가고 이 과정을 거쳐 최종적으로 1에 도달할 수 있는 수를 뜻합니다.

예를 들어,

3이란 숫자가 주어지면 19 -> 82 -> 68 -> 100 -> 1 로 HappyNumber인 것을 확인할 수 있습니다.

4라는 숫자는 4 -> 16 -> 37 -> 56 -> 61 -> 37 순환(Cycle) 고리가 생겨 UnHappyNumber인 것을 볼 수 있습니다.

따라서, 우리는 다음과 같이 알고리즘을 설계할 수 있습니다.

[알고리즘 설계]

1. 어떤 숫자가 주어졌을 때, 각 자릿수를 구하고 제곱해서 더한 값을 return 해주는 함수.

2. 각 자리수를 구하고 제곱해서 더해나가다가 순환(recycle) 고리가 생기는지 체크해주는 함수. 

3. 순환 고리가 생긴다면 UNHAPPY / 순환 고리가 생기지 않고 1이란 숫자가 나타나면 HAPPY 를 출력해주는 함수.

총 3가지 작업이 필요하다는 것을 확인할 수 있습니다.

설계한 알고리즘을 구현해보겠습니다.

#include<iostream>

using namespace std;

int nlist[10] = {};
int repeat[10000000] = {};

int divide(int);
bool check_repeat(int, int);

int main(void) {
	int ninput, count = 0;
	cin >> ninput;
	while (1) {
		repeat[count] = ninput;
		if (ninput == 1) {
			cout << "HAPPY";
			break;
		}
		if (check_repeat(ninput, count) || count == 9999999) {
			cout << "UNHAPPY";
			break;
		}
		ninput = divide(ninput);
		//cout << count << "번 째 : " << ninput << endl;
		count++;
	}
}

/* 자리수별로 자른다. */
/* 자리수별로 제곱해서 더한 값을 return해준다. */
int divide(int ninput) {
	/* 이 부분 예외처리 안해서 틀렸음.*/
	if (ninput < 10) {
		return ninput * ninput;
	}
	int out = 0;
	nlist[0] = ninput / 1000000000;
	nlist[1] = (ninput % 1000000000) / 100000000;
	nlist[2] = (ninput % 100000000) / 10000000;
	nlist[3] = (ninput % 10000000) / 1000000;
	nlist[4] = (ninput % 1000000) / 100000;
	nlist[5] = (ninput % 100000) / 10000;
	nlist[6] = (ninput % 10000) / 1000;
	nlist[7] = (ninput % 1000) / 100;
	nlist[8] = (ninput % 100) / 10;
	nlist[9] = (ninput % 10);
	for (int i = 0; i < 10; i++) {
		if (nlist[i] != 0)
			out += nlist[i] * nlist[i];
	}
	return out;
}

// 지금까지나왔던 값 중에서 현재 값이 있는지 없는지 확인한다.
bool check_repeat(int ninput, int count) {
	for(int i =0 ; i< count; i++){
        if(repeat[i] == ninput)
            return true;
    }
    return false;
}

각 자릿수를 구하는 divide 함수는 https://travelbeeee.tistory.com/4 기존의 포스팅 글을 참고하시면 될 것 같습니다. 

check_repeat 함수는 지금까지 결과로 나왔던 값들을 순회하며 공통된 값이 존재하면 순환(Cycle)고리가 형성된 것이므로 true 아니면 false를 return 해주는 함수입니다.

아마 2017 ACM-ICPC 예선에서 가장 쉬운 문제가 아닐까 싶습니다.

알고리즘 설계하기 굉장히 쉬웠고, 예외만 잘 잡아준다면 쉽게 풀 수 있는 문제인 것 같습니다.