Codetesing의 코딩공부

딱히 어려운것 없이 조건에 따라 시뮬레이션 돌리는 문제같다.

다만 문자열의 괄호 처리를 알맞게 해야 하며 조건을 잘 설정해야 한다.

#include <iostream>

#include <string>
#include <vector>

using namespace std;

bool IS_RIGHT(string s) {
    if(s[0] == ')')
        return false;
    
    int cnt = 1;
    for(int i = 1; i < s.size(); i++)
    {
        if(s[i] == ')')
            cnt--;
        else
            cnt++;
        if(cnt < 0)
            return false;
    }
    
    if(cnt == 0)
        return true;
    else
        return false;
}

string DFS(string s) {
    string u, v;
    
    if(s == "")
        return "";
    
    int cnt = 0;
    
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] == '(')
            cnt++;
        else
            cnt--;
        
        if(cnt == 0)
        {    
            u = s.substr(0, i + 1);
            if(i == s.size() - 1)
                v = "";
            else
                v = s.substr(i + 1, s.size());
            
            if(IS_RIGHT(u))
                return u + DFS(v);
            else
            {
                string temp = "";
                for(int j = 1; j < u.size() - 1; j++)
                {
                    if(u[j] == ')')
                        temp += '(';
                    else
                        temp += ')';
                }
                
                return '(' + DFS(v) + ')' + temp;
            }
        }
    }
}

string solution(string p) {
    string answer = "";
    
    if(p.size() == 0)
        return "";
    
    answer = DFS(p);
    
    return answer;
}

1번문제로 크게 어렵지 않았으며 알고리즘 없는 구현문제이다.

중간값 처리만 잘 해주면 되었고 선택에 따라 점수만 잘 올려주면 쉽게 구현할 수 있을것이다.

#include <string>
#include <vector>

using namespace std;

// RT, CF, JM, AN   < 동의  비동의 >

string solution(vector<string> survey, vector<int> choices) {
    string answer = "";
    string selection[4] = {"RT", "CF", "JM", "AN"};
    int n = survey.size();
    int cnt[26] = {0};

    for(int i = 0; i < n; i++){
        int score = choices[i] - 4;

        if(score < 0)
            cnt[survey[i][0] - 'A'] += score * -1;
        else
            cnt[survey[i][1] - 'A'] += score;
    }

    for(int i = 0; i < 4; i++) {
        if(cnt[selection[i][0] - 'A'] > cnt[selection[i][1] - 'A'])
            answer = answer + selection[i][0];
        else if (cnt[selection[i][0] - 'A'] < cnt[selection[i][1] - 'A'])
            answer = answer + selection[i][1];
        else
        {
            if(selection[i][0] > selection[i][1])
                answer = answer + selection[i][1];
            else
                answer = answer + selection[i][0];
        }
    }

    return answer;
}

크게 어렵지는 않았으나 root N 까지 돌려야 하는걸 한번에 알지못해 시간이 좀 걸렸다.

그외에는 쉬운 문제였다.

#define MAX 1000000000

#include <iostream>
#include <algorithm>

using namespace std;

bool IS_SAME_NUM(int n, int b) {

	int temp = n % b;
	n /= b;

	for (; n != 0; n /= b)
		if (temp != n % b)
			return false;

	return true;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		int Answer = MAX;
		
		int N; cin >> N;

		if (N <= 2)
			Answer = N + 1;

		else
		{
			for (int i = 2; i * i <= N; i++)
			{
				if (IS_SAME_NUM(N, i))
				{
					Answer = min(i, Answer);
				}

				if (N % i != 0)
					continue;

				int temp = N / i - 1;

				if (temp > i)
					Answer = min(temp, Answer);
			}

			if (Answer == MAX)
				Answer = N - 1;
		}
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}

SCPC 1회 첫번째 예선 2번문제였다.

어려운것 없었으며 그대로 시뮬레이션 돌리면 되는 문제였다.

다만 방향설정이 복잡하여 case를 잘 나눠야한다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef struct pos {
	int x;
	int y;
	int dir;
}pos;

pos temp;

void next_pos(int cur)
{
	if (cur == 0)
		temp.x++;
	else if (cur == 1)
		temp.y--;
	else if (cur == 2)
		temp.x--;
	else
		temp.y++;
}

void next(pos cur, char mirror)
{
	temp = cur;

	if (mirror == '1')
	{
		if (cur.dir == 0)
			temp.dir = 1;
		else if (cur.dir == 1)
			temp.dir = 0;
		else if (cur.dir == 2)
			temp.dir = 3;
		else
			temp.dir = 2;
	}

	else if(mirror == '2')
	{
		if (cur.dir == 0)
			temp.dir = 3;
		else if (cur.dir == 1)
			temp.dir = 2;
		else if (cur.dir == 2)
			temp.dir = 1;
		else
			temp.dir = 0;
	}

	next_pos(temp.dir);
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T, test_case;

	cin >> T;

	for (test_case = 0; test_case < T; test_case++)
	{
		int Answer = 0;
		int N; cin >> N;
		vector<string> arr(N);
		vector<vector<bool>> visited(N, vector<bool>(N, false));
		for (int i = 0; i < N; i++)
			cin >> arr[i];

		pos cur = { 0, 0, 3 };
		while (1)
		{
			if(cur.x < 0 || cur.x >= N || cur.y < 0 || cur.y >= N)
				break;

			if (!visited[cur.x][cur.y] && arr[cur.x][cur.y] != '0')
			{
				visited[cur.x][cur.y] = true;
				Answer++;
			}

			next(cur, arr[cur.x][cur.y]);
			cur = temp;
		}

		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}

SCPC 1회 첫번째 예선 1번 문제이다.

알고리즘이 딱히 필요하진 않았으며 case만 잘 나누면 쉽게 풀린 문제였다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		int Answer = 0;
		int N; cin >> N;
		queue<int> A;
		int temp;

		for (int i = 0; i < N - 1; i++)
		{
			cin >> temp;
			A.push(temp);
		}
		int end; cin >> end;
		int K; cin >> K;

		int start = 0;
		int last = -1;
		int cnt = 0;

		while (1)
		{
			if (start + K >= A.front())
			{
				last = A.front();
				A.pop();
			}
			else
			{
				if (last == -1)
					break;

				start = last;
				cnt++;

				if (start + K < A.front())
					break;
			}
			
			if (A.empty())
			{
				if (start + K < end)
				{
					if (last + K >= end)
					{
						start = last;
						cnt++;
						break;
					}
				}
				else
					break;
			}
		}

		if (start + K >= end)
			Answer = cnt + 1;
		else
			Answer = -1;

		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;//Your program should return 0 on normal termination.
}