게임 개발자가 되고 싶어요

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

접근 방법

1. 가장 적게 버튼을 조작해야되니 0은 안눌러도 되고, 1로 나누었을 때, 4-1 순으로 나누었을 때, 8-4-1순으로 나누었을 때로 나누어 계산 - 틀림

2. 문제에 써있지는 않는데 출력 3번을 보면, 버튼 한번에 1로 나누어져서 출력이 30 1이 될 수 있지만 45 4가 출력 됨

   - 가장 적게 누른 순 -> 숫자가 큰 순(내림차순?)

3. 내림차순으로 1개, 2개 3개 구간 나누어지는지 확인 -> 8, 4, 1, 8-4, 8-1, 4-1, 8-4-1

문제 풀이

• 1,4,8의 몫을 담을 변수 생성
• 가장 적게, 내림차순으로 조건문을 돌며 되면 그 조건 사용
• 리스트에 시간 - 1의 몫, 시간 - 4의 몫, 시간 - 8의 몫을 하면 버튼을 누르는 타이밍이 나온것을 넣기 (시간*속도 = 거리, 내림차순이니 1부터 계산해주기)
• 출력형식에 맞게 리스트값 출력

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

namespace Baekjoon.Gold
{
    class _25597
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            //n[0] = X미터, n[1] = T초
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int one_div = 0;
            int four_div = 0;
            int eight_div = 0;
            int count = 0;
            int time = n[1];

            //8
            if (n[0]%8 == 0 && n[0]/8 <= n[1])
                eight_div = n[0]/8;
            //4
            else if (n[0] % 4 == 0 && n[0] / 4 <= n[1])
                four_div = n[0] / 4;
            //1
            else if (n[0] <= n[1])
                one_div = n[0];
            //8 4
            else if ((n[0] % 8) % 4 == 0 && (n[0] / 8) + ((n[0] % 8) / 4) <= n[1])
            {
                eight_div = n[0] / 8;
                n[0] %= 8;
                four_div = n[0] / 4;
            }
            //8 1
            else if ((n[0]/8) + (n[0]%8) <= n[1])
            {
                eight_div = n[0] / 8;
                n[0] %= 8;
                one_div = n[0];
            }
            //4 1
            else if ((n[0] / 4) + (n[0] % 4) <= n[1])
            {
                four_div = n[0] / 4;
                n[0] %= 4;
                one_div = n[0];
            }
            //8 4 1
            else if ((n[0] / 8) + ((n[0] % 8) / 4) + ((n[0] % 8) % 4) <= n[1])
            {
                eight_div = n[0] / 8;
                n[0] %= 8;
                four_div = n[0] / 4;
                n[0] %= 4;
                one_div = n[0];
            }
            else
            {
                Console.WriteLine(-1);
                return;
            }

            int[] arr = {one_div, four_div, eight_div};
            List<(int, int)> list = new List<(int, int)> ();
            for(int i = 0; i<3; i++)
            {
                int num;
                if (i == 0)
                    num = 1;
                else if (i == 1)
                    num = 4;
                else
                    num = 8;    

                if(arr[i] != 0)
                {
                    count++;
                    list.Add((time - arr[i], num));
                    time -= arr[i];
                }
            }

            stb.AppendLine(count.ToString());
            for (int i = list.Count - 1; i >= 0; i--)
                stb.AppendLine($"{list[i].Item1} {list[i].Item2}");

            Console.WriteLine(stb);
        }
    }
}

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

문제는 쉬운데 오타를 발견 못해 오래걸린 문제..

문제 풀이

• 그래프 생성
• 입력받은 단방향 도로를 그래프에 넣기
• 현재 도시가 몇번만에 찾아졌는지 알기위한 번호 배열point_num 생성
• 큐에 시작 도시 삽입, 시작 도시 번호 1
• BFS를 돌며 아직 찾아지지 않았으면(0이면) 큐에 그 도시 넣고, 이전 도시의 번호 +1 해주기
• 도시번호 1번부터 n번까지 돌며 stringbuilder에 번호가 같은 도시 추가

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

namespace Baekjoon.Practice
{
    class _18352
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            //n[0] - 노드 개수, n[1] - 선 개수, n[2] - K, n[3] - 시작
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
            for (int i = 1; i <= n[0]; i++)
                graph[i] = new List<int>();

            for (int i = 0; i < n[1]; i++)
            {
                int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph[arr[0]].Add(arr[1]);
            }

            int[] point_num = new int[n[0] + 1];
            Queue<int> q = new Queue<int>();
            point_num[n[3]] = 1;
            q.Enqueue(n[3]);
            while (q.Count > 0)
            {
                int point = q.Dequeue();
                foreach (int i in graph[point])
                {
                    if (point_num[i] == 0)
                    {
                        point_num[i] = point_num[point] + 1;
                        q.Enqueue(i);
                    }
                }
            }

            bool flag = false;
            for (int i = 1; i <= n[0]; i++)
            {
                if (point_num[i]-1 == n[2]) 
                {
                    stb.AppendLine(i.ToString());
                    flag = true;
                }
            }

            if (flag)
                Console.WriteLine(stb);
            else
                Console.WriteLine(-1);
        }
    }
}

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

접근 방법

1. IO를 n의 개수만큼 반복 +I를 한 io문자열과 입력받은 문자열 S를 반복문으로 돌며 substring하고 서로 비교 - 50점

2. 문자열을 자르지 않고, 카운트를 사용해서 i, i+1, i+2 번째를 계속 비교하며 더해줌 - 인덱스 오류나서 포기

3. 큐에 I의 인덱스를 집어넣고 그 차이가 2이면 카운트를 올리고 n 이상이면 ans++, 차이가 2가 아니면 카운트를 다시 0으로 -100점

문제 풀이

100점 짜리 문제만 풀이

• I 가 나온 위치의 인덱스를 큐에 저장
• 큐에서 하나 리턴 - 이전 I의 인덱스, 반복문을 돌림
• peek와 이전 I의 인덱스가 2이면 IOI 라는 소리니 카운트+1
• 2가 아니면 끊어졌으므로 카운트는 다시 0
• 만약 카운트의 값이 n이상이면 ans에 1을 더해줌 - (==가 아닌 >= 인 이유 : 연속적으로 나오는 것이 있어서)
• 이전 I의 인덱스를 갱신

50점

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

namespace Baekjoon.silver
{
    class _5525
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int len = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            string io = string.Concat(Enumerable.Repeat("IO", n)) + "I";
            //Console.WriteLine(io);

            int iolen = io.Length;
            int ans = 0;
            for(int i = 0; i<len-iolen; i++)
            {
                string s2 = s.Substring(i, iolen);
                if (s2 == io)
                    ans++;
            }
            Console.WriteLine(ans);
        }
    }
}

100점

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

namespace Baekjoon.silver
{
    class _5525
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int len = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            //string io = string.Concat(Enumerable.Repeat("IO", n)) + "I";
            //Console.WriteLine(io);

            Queue<int> que = new Queue<int>();
            for(int i = 0; i<len; i++)
            {
                if (s[i] == 'I')
                    que.Enqueue(i);
            }

            int ans = 0;
            int temp = que.Dequeue(); //이전 I인덱스
            int count = 0;
            while (que.Count > 0)
            {
                if (que.Peek() - temp == 2)
                    count++;
                else
                    count = 0;

                if (count >= n)
                    ans++;

                temp = que.Dequeue();
            }

            Console.WriteLine(ans);
        }
    }
}

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

접근 방법

1. 우선순위 큐에 절댓값을 씌워서 넣어주면 되는거 아닌가? -> 틀림 - 정렬이 되지 않아서

2. 사전으로 키를 절댓값 우선순위, 값을 리스트로 정렬해서 넣어주고 출력 -> 시간초과

3. 도저히 정렬 방법이 떠오르지 않아서 음수와 양수 우선순위 큐 2개 만듬 -> 성공

문제 풀이

정렬 방법이 떠오르지 않아 우선순위 큐 두개를 만들어서 풀었다.

• 입력이 0이 아니면 - 들어온 숫자의 부호에 맞게 양수, 음수 큐에 넣는데, priority는 양수로 넣어줌
• 입력이 0이면 - 일단 두 큐의 개수 확인
• 둘다 큐에 든게 있으면 두개의 peek를 비교하여 절댓값이 더 작은거 deque-출력
• 음수큐에만 든게 있으면 음수 큐 deque-출력
• 양수큐에만 든게 있으면 양수 큐 deque-출력
• 두 큐가 비었으면 0 출력

피드백

도무지 같은 우선순위 내 값을 정렬할 방법이 떠오르지 않았다. 다른 사람들의 풀이를 보니 우선순위^2에 음수면 -1, 양수면 그대로 두어서 푸는 방법이 있다는 것을 알게 되었다.

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

namespace Baekjoon.silver
{
    class _11286
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            int n = int.Parse(Console.ReadLine());
            //양수
            PriorityQueue<int,int> plus = new PriorityQueue<int,int>();
            //음수
            PriorityQueue<int,int> minus = new PriorityQueue<int,int>();

            for(int i = 0; i<n; i++)
            {
                int num = int.Parse(Console.ReadLine());

                if(num == 0)
                {
               		//양,음 둘다 값이 있으면
                    if (minus.Count > 0 && plus.Count > 0)
                    {
                    	//음수의 절댓값이 더 크면 양수꺼 출력
                        if (Math.Abs(minus.Peek()) > Math.Abs(plus.Peek()))
                            stb.AppendLine(plus.Dequeue().ToString());
                        //아니면 음수꺼 출력
                        else
                            stb.AppendLine(minus.Dequeue().ToString());
                    }
                    //음수만 값이 있으면 음수꺼 출력
                    else if (minus.Count > 0)
                        stb.AppendLine(minus.Dequeue().ToString());
                    //양수만 값이 있으면 양수꺼 출력
                    else if (plus.Count > 0)
                        stb.AppendLine(plus.Dequeue().ToString());
                    //둘다 없으면 0 출력
                    else
                        stb.AppendLine("0");
                }
                else
                {
                	//양수면 양수에, 음수면 음수에 넣기
                    if (num > 0)
                        plus.Enqueue(num, num);
                    else
                        minus.Enqueue(num, Math.Abs(num));
                }
            }

            Console.WriteLine(stb);
        }
    }
}