PS 시나브로

문제 : https://www.acmicpc.net/problem/27468

문제 요약

1~N 까지 정확히 한번 사용

인접한 세수 A, B, C가 |A-B| = |B-C| * 2 혹은 |A-B| = |B-C| * 0.5를 만족

문제 분류 : 애드혹

C++

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_27468.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int iN;
	cin >> iN;

	cout << "YES" << "\n";
	if (iN % 4 == 2)
	{
		for (int i = 1; i <= iN; ++i)
		{
			if (i % 4 == 1) cout << (i + 1);
			if (i % 4 == 2) cout << (i - 1);
			if (i % 4 == 3) cout << i;
			if (i % 4 == 0) cout << i;
			cout << (i == iN ? "\n" : " ");
		}
	}
	else
	{
		for (int i = 1; i <= iN; ++i)
		{
			if (i % 4 == 1) cout << i;
			if (i % 4 == 2) cout << (i + 1);
			if (i % 4 == 3) cout << (i - 1);
			if (i % 4 == 0) cout << i;
			cout << (i == iN ? "\n" : " ");
		}
	}

	return 0;
}

문제 풀이

주어진 N을 4 단위로 생각한다.

주어진 N을 4로 나머지연산했을 때 2인 경우

2+4x, 1+4x, 3+4x, 4+4x (x = 0,1,2,3,...)를 반복해서 출력한다.

-> [2 1 3 4] [6 5 7 8] [10 9] 

-> 간격 : 1 2 1 2 1 2 1 2 1 로 반복되게 된다.

주어진 N을 4로 나머지연산했을 때 2가 아닌경우

1+4x, 3+4x, 2+4x, 4+4x (x = 0,1,2,3,...)를 반복해서 출력한다.

-> [1 3 2 4] [5 7 6 8] [9 11 10 12] 

-> 간격 : 2 1 2 1 2 1 2 1 2 1 2 로 반복되게 된다.

문제 : https://www.acmicpc.net/problem/6568

문제 요약 : 프로그램 종료 후 가산기의 값 출력

C++

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_6568.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Fetch(string str)
{
	int iSum = 0;
	for (char ch : str)
	{
		iSum <<= 1;
		iSum += ch - '0';
	}
	return iSum;
}

void Decode(const int command, int& _operator, int& _operand)
{
	_operator = command >> 5;
	_operand = command % 32;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vecMemory(32, 0);
	int iIndex = 0;

	string strCommand;
	while (cin >> strCommand)
	{
		vecMemory[iIndex] = Fetch(strCommand);
		iIndex = (iIndex + 1) % 32;

		if (iIndex == 0)
		{
			int iPC = 0;
			int iSum = 0;

			while (iPC >= 0)
			{
				int iTempPC = iPC;
				int iOperator, iOperand;
				Decode(vecMemory[iPC], iOperator, iOperand);
				iPC = (iPC + 1) % 32;
				switch (iOperator)
				{
				case 0: vecMemory[iOperand] = iSum; break;
				case 1: iSum = vecMemory[iOperand]; break;
				case 2: iPC = (iSum == 0 ? iOperand : iPC); break;
				case 3: break;
				case 4: if (--iSum < 0) iSum += 256; break;
				case 5: iSum = (++iSum) % 256; break;
				case 6: iPC = iOperand; break;
				case 7: iPC = -1; break;
				}
			}

			for (int i = 7; i >= 0; --i)
			{
				cout << ((iSum & (1 << i)) == (1 << i) ? "1" : "0");
			}
			cout << "\n";
		}
	}
	return 0;
}

시스템 프로그래밍 공부에 좋은 문제인 것 같아서 풀어 보았다.

우선 받은 명령어를 RAM 에 적재하듯이 올려준다. (Load)

RAM과 CPU에서는 크게 Fetch - Decode - Execute 가 일어나게 된다.

이를 기반으로 알고리즘을 작성하면 된다.

1. 해당 PC가 가리키는 명령어를 operator와 operand로 분리한다.

2. 명령어 해석후에 PC레지스터 의 값을 1 증가시키며 이때 32보다 커지면 0으로 만들어 준다.

3. operator에 따른 명령을 수행한다.

이 문제에서 눈여겨 볼 점은 명령을 통해 직접 계산을 하였을 경우

총 5비트밖에 사용하지 못하기 때문에 32가 넘어가는 숫자에 대한 연산을 할 수 없지만

값의 주소를 이용해 연산 횟수는 늘지만 8비트 모두 연산에 사용할 수 있다.

이 방법은 Indirect 모드라고 볼 수 있다.

문제 : https://www.acmicpc.net/problem/27516

문제 요약 : 특정 속도로 던졌을 때 맞출 수 있는 과녁의 최대 개수 출력

C++

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_27516.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long gcd(long long lA, long long lB)
{
	if (lB % lA == 0) return lA;
	return gcd(lB % lA, lA);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long lX, lY;
	cin >> lX >> lY;

	vector<pair<long long, long long>> vecMinus;
	vector<pair<long long, long long>> vecPlus;

	int iN;
	cin >> iN;
	while (iN--)
	{
		long long lTempX, lTempY;
		cin >> lTempX >> lTempY;

		lTempX -= lX;
		lTempY -= lY;
		if (lTempX == 0 || lTempY >= 0) continue;

		if (lTempX < 0)
		{
			lTempX = abs(lTempX) * abs(lTempX);
			lTempY = abs(lTempY);
			long long lGCD = (lTempX < lTempY ? gcd(lTempX, lTempY) : gcd(lTempY, lTempX));
			lTempX /= lGCD;
			lTempY /= lGCD;
			vecMinus.push_back({ lTempX, lTempY });
		}
		else
		{
			lTempX = abs(lTempX) * abs(lTempX);
			lTempY = abs(lTempY);
			int lGCD = (lTempX < lTempY ? gcd(lTempX, lTempY) : gcd(lTempY, lTempX));
			lTempX /= lGCD;
			lTempY /= lGCD;
			vecPlus.push_back({ lTempX, lTempY });
		}
	}

	int iAns = 0;
	if (vecMinus.size() > 0)
	{
		sort(vecMinus.begin(), vecMinus.end(), [](pair<long long, long long> o1, pair<long long, long long> o2)->bool
			{
				if (o1.first == o2.first)
				{
					return o1.second < o2.second;
				}
				return o1.first < o2.first;
			});

		iAns = max(iAns, 1);
		int iCount = 1;
		int iSize = vecMinus.size();
		for (int i = 1; i < iSize; ++i)
		{
			if (vecMinus[i].first == vecMinus[i - 1].first && vecMinus[i].second == vecMinus[i - 1].second)
			{
				++iCount;
			}
			else
			{
				iCount = 1;
			}
			iAns = max(iAns, iCount);
		}
	}
	if (vecPlus.size() > 0)
	{
		sort(vecPlus.begin(), vecPlus.end(), [](pair<long long, long long> o1, pair<long long, long long> o2)->bool
			{
				if (o1.first == o2.first)
				{
					return o1.second < o2.second;
				}
				return o1.first < o2.first;
			});
		iAns = max(iAns, 1);
		int iCount = 1;
		int iSize = vecPlus.size();
		for (int i = 1; i < iSize; ++i)
		{
			if (vecPlus[i].first == vecPlus[i - 1].first && vecPlus[i].second == vecPlus[i - 1].second)
			{
				++iCount;
			}
			else
			{
				iCount = 1;
			}
			iAns = max(iAns, iCount);
		}
	}
	cout << iAns << "\n";
	return 0;
}

과녁의 위치에서 사격자의 위치를 빼서 상대위치로 변환해준다.

발사자는 x축에 평행하게 던지므로 x값이 0인 경우를 제외 한다.

중력이 작용하기 때문에 y값이 0과 같거나 큰 경우를 제외 한다.

x의 위치가 음수인 경우는 양수인 경우와 동시에 맞출 수 없다.

마찬가지로 양수인 경우는 음수인 경우와 동시에 맞출 수 없다.

그러므로 두개의 집합으로 따로 생각 해 준다.

t(시간) 이후 X와 Y의 좌표는 다음과 같다.

x = v_x * t

y = 0.5 * g * t^2

따라서 v_x의 속도로 발사 했을 때 저 그래프에 있는 과녁은 모두 동시에 맞게 된다.

이것을 확인하기 위해 x를 제곱하여 선형적으로 확인 할 수 있게 한다

즉, x^2/y 값이 같은 경우 동시에 맞는다 이것을 기약분수로 나타내기 위해

유클리드 호제법을 이용해 분모분자를 나누고 기록 해둔다

기록한 값들을 내림차순 혹은 오름차순으로 정리하고

같은 개수를 체크 해 가장 많은 개수가 나온 경우를 출력한다

문제 : https://www.acmicpc.net/problem/12933

문제 요약 : 녹음한 소리에 필요한 오리의 최소 마리수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_12933.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int[] arr = new int[6];
        int sz = str.length();
        int mx = 0;
        arr[0] = sz;
        for (int i = 0; i < sz; i++) {
            int n = 0;
            if (str.charAt(i) == 'q') n = 1;
            if (str.charAt(i) == 'u') n = 2;
            if (str.charAt(i) == 'a') n = 3;
            if (str.charAt(i) == 'c') n = 4;
            if (str.charAt(i) == 'k') n = 5;
            if (arr[n - 1] == 0) {
                System.out.println("-1");
                return;
            }
            arr[n]++;
            arr[n - 1]--;
            mx = Math.max(mx, arr[1] + arr[2] + arr[3] + arr[4]);
        }
        if (arr[5] * 5 != sz) {
            System.out.println("-1");
            return;
        }
        System.out.println(mx);
    }
}

q, u, a, c, k 를 1, 2, 3, 4, 5라고 할 때

1. 해당 음성에서 n-1은 n보다 같거나 많이 나와야 한다.

2. 해당 음성에서 최대로 필요한 오리의 수는 1, 2, 3, 4의 합이다 (5는 이미 끝났기 때문에 필요가 없다)

3. 마지막으로 5번이 음성의 길이의/5 횟수만큼 나와야 한다.

위 세 조건을 만족시키도록 알고리즘을 짜서 만족하지 않을 경우 "-1"을 출력하고

주어진 음성이 주어진 조건을 만족한다면 계산 도중에 필요한 오리의 수의 최댓값을 출력한다.

ex) quqaquuacakcqckkuaquckqauckack

문제 : https://www.acmicpc.net/problem/2687

문제 요약 : 해당 문자열을 디코딩하여 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2687.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int p = Integer.parseInt(br.readLine());
        while (p-- > 0) {
            StringBuilder tsb = new StringBuilder();
            int b = Integer.parseInt(br.readLine());
            char[] ch = new char[b * 2];
            int cnt = 0;
            for (int i = 0; i < (b + 39) / 40; i++) {
                String str = br.readLine();
                int sz = str.length();
                for (int j = 0; j < sz; j++) ch[cnt++] = str.charAt(j);
            }
            cnt = 0;
            for (int i = 0; i < b * 2; ) {
                int repeat = 0;
                if (ch[i] >= 'A' && ch[i] <= 'F') {
                    repeat += ch[i] - 'A' + 10;
                } else {
                    repeat += ch[i] - '0';
                }
                repeat *= 16;
                if (ch[i + 1] >= 'A' && ch[i + 1] <= 'F') {
                    repeat += ch[i + 1] - 'A' + 10;
                } else {
                    repeat += ch[i + 1] - '0';
                }
                if (repeat >= 128) {
                    repeat -= 125;
                    while (repeat-- > 0) {
                        if (cnt % 40 == 0) tsb.append("\n");
                        tsb.append(ch[i + 2] + "" + ch[i + 3]);
                        cnt++;
                    }
                    i += 4;
                } else {
                    repeat++;
                    i += 2;
                    while (repeat-- > 0) {
                        if (cnt % 40 == 0) tsb.append("\n");
                        tsb.append(ch[i] + "" + ch[i + 1]);
                        i += 2;
                        cnt++;
                    }
                }
            }
            sb.append(cnt + "" + tsb);
            if (p > 0) sb.append("\n");
        }
        System.out.println(sb);
    }
}

우선 입력이 80개의 문자로 쪼개져서 들어오기 때문에

나누어진 문자열을 하나의 char[] 배열에 담아준다.

이때 문자는 2개가 하나의 글자를 나타내게 된다.

글자를 하나하나 씩 보며

해당 글자의 값을 숫자로 반환하였을 때 의 값을 repeat이라고 할때

반환할경우 8비트의 범위(0~255)의 값을 가지게 된다.

1. repeat >= 128(1000 0000)인 경우

repeat-125 번 만큼 다음 글자를 저장한다.

저장 도중 저장된 글자의 길이가 80자로 나눠 나머지가 없을경우 줄내림(\n) 을 더해준다.

2. repeat < 128(1000 0000)인 경우

숫자로 반환한 글자의 다음글자 기준으로 repeat+1의 길이의 글자를 저장한다. 

저장 도중 저장된 글자의 길이가 80자로 나눠 나머지가 없을경우 줄내림(\n) 을 더해준다.

문제 : https://www.acmicpc.net/problem/2686

문제 요약 : 해당 문자열을 인코딩하여 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2686.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int p = Integer.parseInt(br.readLine());
        while (p-- > 0) {
            int b = Integer.parseInt(br.readLine());
            int cnt = 0;
            char[] ch = new char[b * 2];
            for (int i = 0; i < (b + 39) / 40; i++) {
                String str = br.readLine();
                int sz = str.length();
                for (int j = 0; j < sz; j++) ch[cnt++] = str.charAt(j);
            }
            int sz = 0;
            String ans = "";
            StringBuilder tsb = new StringBuilder();
            for (int i = 0; i < b; i++) {
                if (i + 2 < b) {
                    if ((ch[i * 2] == ch[i * 2 + 2]) && (ch[i * 2 + 1] == ch[i * 2 + 3]) && (ch[i * 2] == ch[i * 2 + 4]) && (ch[i * 2 + 1] == ch[i * 2 + 5])) {
                        if (sz != 0) {
                            ans = ans + numtoch(sz - 1) + tsb.toString();
                            tsb = new StringBuilder();
                        }
                        sz = 3;
                        while (true) {
                            if (i + sz >= b || sz == 130) break;
                            if (ch[i * 2] == ch[i * 2 + sz * 2] && ch[i * 2 + 1] == ch[i * 2 + sz * 2 + 1]) {
                                sz++;
                            } else {
                                break;
                            }
                        }
                        ans = ans + numtoch(sz + 125) + ch[i * 2] + ch[i * 2 + 1];
                        i += sz - 1;
                        sz = 0;
                        continue;
                    }
                }
                sz++;
                tsb.append(ch[i * 2] + "" + ch[i * 2 + 1]);
                if (sz == 128) {
                    ans = ans + numtoch(sz - 1) + tsb.toString();
                    sz = 0;
                    tsb = new StringBuilder();
                }
            }
            if (sz != 0) ans = ans + numtoch(sz - 1) + tsb.toString();
            sb.append(ans.length() / 2 + "\n");
            for (int i = 0; i < (ans.length() + 79) / 80; i++) {
                sb.append(ans.substring(i * 80, Math.min((i + 1) * 80, ans.length())) + "\n");
            }
        }
        System.out.println(sb);
    }

    private static String numtoch(int n) {
        int a = n / 16;
        int b = n % 16;
        char A = ' ';
        char B = ' ';
        if (a >= 10) {
            A = (char) ('A' + a - 10);
        } else {
            A = (char) ('0' + a);
        }
        if (b >= 10) {
            B = (char) ('A' + b - 10);
        } else {
            B = (char) ('0' + b);
        }
        return A + "" + B;
    }
}

우선 입력이 80개의 문자로 쪼개져서 들어오기 때문에

나누어진 문자열을 하나의 char[] 배열에 담아준다.

이때 문자는 2개가 하나의 글자를 나타내게 된다.

글자를 하나하나 씩 보며

A. 해당 글자가 다음 글자와 그다음 글자와 같을 경우

 저장된 글자의 크기(함수를 통해 변환)와 저장된 글자를 ans에 더해준다.

 해당 글자가 얼마나 길게 다음 글자와 같은지 계산한다

 계산 도중 같은 글자가 130자를 넘어갈 경우 종료한다.

 저장된 글자의 크기(함수를 통해 변환)와 해당 글자를 ans에 더해준다.

B. 해당 글자가 다음 글자와 그 다음글자와 다를경우, 다음글자 혹은 그다음 글자가 없을 경우

 해당 글자를 저장해준다.

 계산 도중 저장된 글자가 128자가 될 경우

 저장된 글자의 크기(함수를 통해 변환)와 해당 글자를 ans에 더해준다.

모든 글자를 확인 후 저장된 글자가 있을 경우

저장된 글자의 크기(함수를 통해 변환)와 해당 글자를 ans 에 더해준다.

마지막으로 80 글자씩 잘라주어 출력한다.

문제 :  https://www.acmicpc.net/problem/16634

문제 요약 : 해당 문자열을 인코딩 혹은 디코딩하여 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_16634.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        if (st.nextToken().charAt(0) == 'E') {
            String str = st.nextToken();
            int cnt = 1;
            sb.append(str.charAt(0));
            int sz = str.length();
            for (int i = 1; i < sz; i++) {
                if (str.charAt(i) == str.charAt(i - 1)) {
                    cnt++;
                } else {
                    sb.append(cnt + "" + str.charAt(i));
                    cnt = 1;
                }
            }
            sb.append(cnt);
        } else {
            String str = st.nextToken();
            int sz = str.length();
            for (int i = 0; i < sz; i += 2) {
                for (int j = str.charAt(i + 1); j > '0'; j--) {
                    sb.append(str.charAt(i));
                }
            }
        }
        System.out.println(sb);
    }
}

인코딩의 경우

우선 1 번째 문자를 StringBuilder에 더해준 후 cnt 의 값을 1로 초기화 한다.

그 후 주어진 문자열의 2 번째 문자 부터 확인하며

- 이전 문자와 같을 경우 cnt 값을 1 증가시켜 준다.

- 이전 문자와 다를 경우 cnt 값과 해당 문자열을 StringBuilder에 더해 주고

  cnt 값을 1로 초기화한다.

문자열 확인이 끝나면 StringBuilder에 cnt 값을 더해주고 출력해준다.

디코딩의 경우

주어진 문자열을 2 개 단위로 확인하며 뒤에 주어진 숫자 만큼

앞의 문자열을 StringBuilder에 더해준 후에 출력한다.

문제 : https://www.acmicpc.net/problem/13772

문제 요약 : 해당 문자열 알파벳에 있는 구멍의 총 개수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_13772.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int[] arr = {1,2,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0};
		int n,i,sz,s;
		n = Integer.parseInt(br.readLine());
		while(n-->0) {
			String str = br.readLine();
			sz = str.length();
			s = 0;
			for(i=0;i<sz;i++) if(str.charAt(i)>='A'&&str.charAt(i)<='Z') s += arr[str.charAt(i)-'A'];
			sb.append(s+"\n");
		}
		System.out.println(sb);
	}
}

A, D, O, P, Q, R의 경우 1개

B 의 경우 2개

그 외 0 개

로 전처리 후 계산해준다.