Hostramus

1. 문제

- [백준 C#] 1316번 그룹 단어 체커 (C#)  (https://www.acmicpc.net/problem/1316)

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

2. 문제 포인트

• 문자열 입력 받기
• 각 문자열의 첫글자부터 반복여부 확인하기
• 전체 a~b까지 반복 여부를 확인 할 필요 없이 단어에 있는 알파벳만 확인

3. 전체 코드

using System;
using System.Linq;

namespace S5_01316번
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int cnt = int.Parse(Console.ReadLine());

            int result = 0;

            // 개수 카운팅을 위한 flag
            bool flag = false;


            for (int i = 0; i < cnt; i++)
            {
                string word = Console.ReadLine();
                string word2 = word;

                if (word.Length == 1)
                {
                    flag = true;
                }
                else {
                    foreach (var a in word)
                    {
                        // 문자열 포함 여부를 확인하여 검증하기 위해 첫글자를 지우고 해당 문자가 뒤에 다른 그룹을 형성하는지 확인
                        word2 = word2.Remove(0, 1);

                        flag = true;

                        if (word2.Length == 0)
                        {
                            break;
                        }
                        else
                        {
                            // 맨 앞글자가 같은 문자인 경우는 검증 건너뜀
                            // ex. aabcd는 a를 지웠지만 다음 글자가 a기에 아래 검증이 의미가 없음
                            if (word2[0] != a)
                            {
                                // 맨 앞글자를 제외한 다른 곳에서 값이 발견되면 그룹 문자 조건에 위배
                                if (word2.Contains(a))
                                {
                                    // 떨어져 있는 그룹에 해당 문자가 있는 경우
                                    // 카운팅이 되지 않고 로직 종료
                                    flag = false;
                                    break;
                                }
                            }
                        }
                    }
                }


                if (flag)
                {
                    result++;
                }

                // flag 초기화
                flag = false;
            }


            Console.WriteLine(result);
        }
    }
}

// 1316번 그룹 단어 체커
// https://www.acmicpc.net/problem/1316

1. 문제

- [백준 C#] 2941번 크로아티아 알파벳 (C#)  (https://www.acmicpc.net/problem/2941)

예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다.

크로아티아 알파벳변경

예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.

dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj와 nj도 마찬가지이다. 위 목록에 없는 알파벳은 한 글자씩 센다.

2. 문제 포인트

• 단어 입력 받기
• 크로아티아 알파벳에 해당하는 문자열을 '1'로 바꾸기
  이유 : 다른 알파벳 a나 b등으로 바꾸면 또 다른 크로아티아 알파벳 조합이 만들어 질 수 있으므로 전혀 관계없는 1로 변환
• 변환이 완료된 문자의 문자열 개수 출력

3. 전체 코드

using System;
using System.Linq;

namespace S5_02941번
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string word = Console.ReadLine();

            word = word.Replace("c=", "1");
            word = word.Replace("c-", "1");
            word = word.Replace("dz=", "1");
            word = word.Replace("d-", "1");
            word = word.Replace("lj", "1");
            word = word.Replace("nj", "1");
            word = word.Replace("s=", "1");
            word = word.Replace("z=", "1");

            Console.WriteLine(word.Count());
        }
    }
}

// 2941번 크로아티아 알파벳
// https://www.acmicpc.net/problem/2941

1. 문제

- [백준 C#] 1157번 단어 공부 (C#)  (https://www.acmicpc.net/problem/1157)

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

2. 문제 포인트

• 단어 입력 받기
• 가장 많이 사용된 알파벳 출력
• 최다 사용 알바벳이 두개인 경우 물음표 출력

3. 전체 코드

using System;
using System.Collections.Generic;
using System.Linq;

namespace B1_01157번
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string word = Console.ReadLine();

            List<int> cnt = new List<int>( Enumerable.Repeat<int>(0, 26).ToArray() );

            word = word.ToUpper();
            
            foreach (var a in word)
            {
                cnt[Convert.ToInt32(a)-65] += 1;
            }

            // LINQ 쿼리문을 이용해 최대값을 가진 요소의 개수를 구하기
            int linq_query = cnt.Where(n => n == cnt.Max()).Count() ;

            // 최댓값이 2개인 경우 필터
            if (linq_query>1)
            {
                Console.WriteLine("?");
            }
            else
            {
                // 아스키 코드를 이용해 해당 인덱스의 값 출력
                int co = 65 + cnt.IndexOf(cnt.Max());
                byte[] a = new byte[] { byte.Parse(co.ToString()) };
                Console.WriteLine(System.Text.Encoding.ASCII.GetString(a) );
            }
        }
    }
}

// 1157번 단어 공부
// https://www.acmicpc.net/problem/1157

1. 문제

- [백준 C#] 2908번 상수 (C#)  (https://www.acmicpc.net/problem/2908)

상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 개를 칠판에 써주었다. 그 다음에 크기가 큰 수를 말해보라고 했다.

상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다.

두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오.

2. 문제 포인트

• 두 숫자를 입력 받는다
• 숫자 두개를 거꾸로 뒤집는다
• 뒤집힌 숫자 두개중 큰 수를 출력한다

3. 전체 코드

using System;
using System.Linq;

namespace B2_02908번
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] num = Console.ReadLine().Split();
            
            // 뒤집은 숫자를 저장할 변수
            string[] reverse_num = new string[] { "", ""};

            // 숫자 뒤집기
            for (int i = 0; i < 3; i++)
            {
                reverse_num[0] += num[0][2 - i];
                reverse_num[1] += num[1][2 - i];
            }

            // 두 숫자중 큰 수를 출력
            Console.WriteLine(reverse_num.Max());
        }
    }
}

// 2908번 상수
// https://www.acmicpc.net/problem/2908

1. 문제

    1789번 수들의 합 (https://www.acmicpc.net/problem/1789)

2. 문제 포인트

• 중복되지 않는 자연수 개수 구하기

3. 접근법

• S를 자연수로 하나씩 빼면서 총 개수를 구한다
• 1, 2, 3... 숫자 하나씩을 S에서 빼면서 계산하다가 뺄 수(n)보다 S의  나머지가 작은 경우 반복문을 종료한다.
  ex. 15인 경우
         15 - 1 - 2 - 3 - 4 - 5  = 0  >> 5번
         17 - 1 - 2 - 3 - 4 - 7 = 0  >>  5번
           - 1~5까지 빼면 17은 2가 남게 됨
           - 1~4까지 빼고 7을 빼면 중복되지 않은 자연수들로 계산이 가능

4. 결과 코드

import sys

a = int(sys.stdin.readline().strip())

# 숫자 사용 횟수
cnt = 0
# 계산에 사용될 숫자
num = 1

while True:
    # 입력받은 숫자에서 1부터 하나씩 빼서 숫자 사용 횟수 계산
    a -= num
    cnt += 1
    num += 1

    # 1부터 1씩 증가한 num이 a의 나머지값보다 크면 숫자가 중복되어 사용되기에
    # num이 a보다 크게 되는 경우 루프 종료
    if num > a:
        break

print(cnt)

# 1789번 수들의 합
# https://www.acmicpc.net/problem/1789

1. 문제

    1439번 뒤집기 (https://www.acmicpc.net/problem/1439)

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

2. 문제 포인트

• 0과 1로 이루어진 문자열 입력
• 모두 같은 숫자로 만들기 (0, 1 무관)
• 한번에 근접한 문자 같이 뒤집기 가능

3. 접근법

• 모든 숫자를 0으로 만들때와 1로 만들때를 구한 후 작은 값 출력
• 전체를 1을 만드는 뒤집기 횟수 ==  split("0")으로 리스트를 생성한 후 만든 요소의 개수
• 전체를 0을 만드는 뒤집기 횟수 ==  split("1")으로 리스트를 생성한 후 만든 요소의 개수
• min()으로 두가지 경우 중 작은 값 출력

4. 결과 코드

import sys

a = sys.stdin.readline().strip()

# 1, 0을 기준으로 문자열을 나눠 리스트 만들기
## list comprehension을 이용하여 내용없는 요소는 제거
b = [bb for bb in a.split("1") if bb]
c = [cc for cc in a.split("0") if cc]

print(min(len(b), len(c)))

# 1439번 뒤집기
# https://www.acmicpc.net/problem/1439

1. 문제

    문제번호 문제 타이틀 (https://www.acmicpc.net/problem/14916)

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

2. 문제 포인트

• 동전은 2원, 5원만 있다
• 동전의 최소 개수를 구한다

3. 접근법

• 이전에 했던 거스름돈 문제와의 차이점
  - 이전문제 : https://hostramus.tistory.com/148
  - 동전이 5원과 2원 2가지다 (point. 5원은 2원의 배수가 아니다)
  - 13원인경우 5 * 1 + 2 * 4 = 13이다 (5원동전을 무조건 먼저 사용해선 안된다)
     ex 1. 13원 = 5 * 1 + 2 * 4  (잔액이 10보다 크지만 5원동전 2개 불가)
     ex 1. 21원 = 5 * 3 + 2 * 3  (잔액이 10보다 크지만 5원동전 4개 불가)
• 2원의 개수를 0개부터 한개씩 늘려가면서 계산한다.

4. 결과 코드

import sys

a = int(sys.stdin.readline().strip())

cnt = 0

while a>0:
    # 입력받은 a값이 5의 배수면 5원짜리로 거슬러주는것이 가장 작은 동전수
    if a % 5 == 0:
        cnt += a // 5
        break
    # 5원짜리로 안될때 2원짜리를 한개씩 늘려가며 최소 개수를 찾기
    else:
        a -= 2
        cnt += 1
        if a < 0:
            cnt = -1

print(cnt)

# 14916번 거스름돈
# https://www.acmicpc.net/problem/14916

1. 문제

    17224번 APC는 왜 서브태스크 대회가 되었을까?  (https://www.acmicpc.net/problem/17224)

2019년 올해도 어김없이 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)가 열렸다! 올해 새롭게 APC의 총감독을 맡게 된 준표는 대회 출제 과정 중 큰 고민에 빠졌다. APC에 참가하는 참가자들이 너무 다양해 대회 문제 난이도 설정이 너무 어렵기 때문이다.

APC는 프로그래밍 대회에 익숙하지 않은 학생들과 전공생이 아닌 학생들도 대거 참가하기 때문에 모두가 풀거나 도전할 수 있는 난이도 커브를 갖춰야 한다. 또한 '경인지역 6개대학 연합 프로그래밍 경시대회 shake!'에 참가할 학교 대표 10인을 선발하기 위한 대표 선발전으로서의 변별력도 갖추어야 하며, 외부인들이 따로 참가할 수 있는 Open Contest가 동시에 진행되기 때문에 소위 '고인물'들에게 한 시간도 안되어 대회가 정복당하는 일도 막고 싶다. 여기에 APC 출제진인 준표, 만영, 현정, 준서는 문제를 준비하는 데 무척 고생을 했기 때문에 참가자들이 모든 문제를 한번씩은 읽어주었으면 하는 소망도 가지고 있다.

욕심 그득한 준표는 고민끝에 이 수많은 니즈를 충족시키기 위한 한가지 해결책을 제안했다. 하나의 문제를 제한조건을 통해 쉬운 버전과 어려운 버전으로 나누어 쉬운 버전만 맞더라도 부분점수를 주는 서브태스크 문제로 대회를 구성하는 것이다. 또한 이렇게 만들어진 문제를 쉬운 버전의 난이도순으로 배치하려 한다.

위와 같이 문제를 준비하면 프로그래밍 대회에 익숙하지 않은 사람은 앞에서부터 따라가면서 도전해볼 수 있어 쉬운 문제를 찾는 데 시간을 쓰지 않을 수 있고, 어려운 버전으로 학교 대표 선발을 위한 변별력을 유지할 수 있으며, 모든 문제가 읽히길 바라는 출제진의 소망도 이룰 수 있을 것이다!

<그림1> 출제중 평가한 문제들의 난이도 예시 (예제2)

<!-- 아래 이야기는 팩션입니다. -->

현정이는 APC에 한 번이라도 나가보고 싶다는 소망이 있다. 하지만 이 소망은 여태까지 단 한 번도, 그리고 앞으로도 이루어질 리 없기 때문에 현정이가 입버릇처럼 하게 된 말이 있는데...

• 현정 : 아~~ 나도 APC 참가만 했으면 상금 받는 건데~~~~~
• 준표 : ... 그건 아닌 것 같은데?

현정이의 근거 없는 자신감이 눈꼴신 준표는 출제 중에 평가한 문제 난이도를 통해 현정이의 예상 점수를 알려주고 현정이가 현실을 받아들일 수 있도록 도와주고자 한다.

현정이는 L 만큼의 역량을 가지고 있어 L보다 작거나 같은 난이도의 문제를 풀 수 있다. 또한 현정이는 코딩이 느리기 때문에 대회 시간이 부족해 K개보다 많은 문제는 해결할 수 없다. 어떤 문제에 대해 쉬운 버전을 해결한다면 100점을 얻고, 어려운 버전을 해결한다면 여기에 40점을 더 받아 140점을 얻게 된다. 어려운 버전을 해결하면 쉬운 버전도 같이 풀리게 되므로, 한 문제를 해결한 것으로 계산한다.

현정이가 APC에 참가했다면 최대 몇점을 얻을 수 있었을지 알려주자.

2. 문제 포인트

• 1행에 "문제 개수, 역량, 풀이 가능한 문제 수" 를 입력 받음
• 2행부터는 쉬운버전 난이도 + 어려운 버전 난이도를 입력 받음
• 현정이가 받을 수 있는 최고 점수를 계산

3. 접근법

• 어려운 난이도까지 풀 수있는 문제(140점 짜리)를 먼저 푼다
  - 어려운문제까지 풀어도 문제 풀이 시간은 1로 계산된다
  - 다시말해 입력을 받을때마다 점수를 계산하면 최대값을 얻을 수 없다
• ex. 풀수 있는 문제 수(K) < 풀 수 있는 140점 문제 수
        - 위와 같은 경우 140 * K점수가 최대 점수가 된다

4. 결과 코드

import sys

a = list(map(int, sys.stdin.readline().split()))
sub = 0
basic = 0

# 문제수(a[0])만큼 반복
for _ in range(a[0]):
    b = list(map(int, sys.stdin.readline().split()))

    # 전체 문제 중 어려운버전까지 풀 수 있는 문제 수 계산
    # 최종 합계에 점수를 더해버리면 안된다.
    if a[1] >= b[1]:
        sub += 1
    # 전체 문제 중 쉬운 버전만 풀 수 있는 문제 수 계산
    elif a[1] >= b[0]:
        basic += 1

# 어려운 문제를 푼 수를 점수로 환산
# '풀 수 있는 문제 수' vs '풀이 가능한 총 문제 수'중 작은 값 선택
## ex. 3문제 풀이 가능 시간, 5개의 어려운 문제 풀이 가능 능력인 경우 어려운 문제 3개만 풀이가 가능(시간 제한)
score = 140 * min(sub, a[2])

# 위에서 어려운 문제를 다 푼뒤 더 풀 시간이 있는 경우 쉬운 문제 풀이
## 풀이 가능 숫자 * 100점을 계산
if a[2] - sub > 0:
    score += 100 * min(basic, (a[2] - sub))

print(score)


# https://www.acmicpc.net/problem/17224