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

 

1110번: 더하기 사이클

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음,

www.acmicpc.net

 

#전체 코드

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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            
            //새로운 수 만들기 -> 새로운 수 비교 

            string input = Console.ReadLine();

            int repeat = 1;
            int[] array = new int[100]; //비교할 값들을 저장
            int count = 1; 
            array[0] = int.Parse(input);//첫번쨰 배열에는 처음 입력값 저장
            string inputFirstNumber, inputSecondNumber;
            int newNumber,final;

            while (repeat ==1)
            {
                if (int.Parse(input) < 10)
                {
                    
                    inputSecondNumber = input.Substring(0, 1);

                    final = int.Parse(inputSecondNumber) * 10 + int.Parse(inputSecondNumber);
                    array[count] = final;

                }
                else
                {
                    inputFirstNumber = input.Substring(0, 1);
                    inputSecondNumber = input.Substring(1, 1);
                    newNumber = int.Parse(inputFirstNumber) + int.Parse(inputSecondNumber);

                    string stringNewNumber = newNumber.ToString();
                    string newSecondNumber;

                    if (newNumber < 10)
                    {
                        newSecondNumber = stringNewNumber.Substring(0, 1);
                    }
                    else
                    {
                        newSecondNumber = stringNewNumber.Substring(1, 1);
                    }
                    

                    final = (int.Parse(inputSecondNumber) * 10) + int.Parse(newSecondNumber);
                    array[count] = final;


                }




                //새로운 수 비교

                for (int i = 0; i < count; i++)
                {
                    if (array[i] == array[count])
                    {
                        Console.WriteLine("{0}", count);
                        repeat = 0;

                    }
                }

                count++;

                input = final.ToString();
                
            }

            
               
            

        }
    }
}

'[백준] > C#' 카테고리의 다른 글

백준 1193번 분수찾기 [C#]  (0) 2023.08.05
백준 1152번 단어의 개수 [C#]  (0) 2023.08.05
백준 1065번 한수 [C#]  (2) 2023.08.05

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

 

1065번: 한수

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나

www.acmicpc.net

한수

 

전체 코드

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

namespace ConsoleApp1
{
    class Program
    {



        static public void Main(string[] args)
        {
            string getA = (Console.ReadLine());

            //각리수의 숫자를 뽑아내서 배열에 저장 -> 차이를 비교해서 저장
            //99까지는 어차피 한수니까 예외처리하자

            Console.WriteLine(Aberration(getA));
            Console.ReadKey();


        }

        static int Aberration(string d)
        {


            int count = 99;
            int[] arrayA = new int[1001];

            //예외처리
            if (d.Length > 2 && d.Length < 5)
            {
                //100부터 입력숫자까지 한수계산
                for (int e = 100; e <= int.Parse(d); e++)
                {

                    string insA = e.ToString();

                    for (int i = 0; i < insA.Length; i++)
                    {
                        arrayA[i] = int.Parse(insA[i].ToString());
                    }

                    //3자리수 아니면 1000 이다. 3자리수일때만 처리하면 더 편할거다.
                    if(insA.Length != 4)
                    {
                        //커지는 등차수열 작아지는 등차수열 구분
                        if (arrayA[0] >= arrayA[1] && arrayA[1] >= arrayA[2])
                        {

                            if ((arrayA[0] - arrayA[1]) == (arrayA[1] - arrayA[2]))
                            {
                                count++;
                            }

                        }

                        if (arrayA[0] < arrayA[1] && arrayA[1] < arrayA[2])
                        {


                            if ((arrayA[1] - arrayA[0]) == (arrayA[2] - arrayA[1]))
                            {
                                count++;
                            }

                        }
                    }


                    
                }
                return count;

            }
            

            return int.Parse(d);

           
        }
    }
}

'[백준] > C#' 카테고리의 다른 글

백준 1193번 분수찾기 [C#]  (0) 2023.08.05
백준 1152번 단어의 개수 [C#]  (0) 2023.08.05
백준 1110번 더하기 사이클 [C#]  (0) 2023.08.05

 

전체 코드

#include<vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

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

    int arr[10001] = { 0, };
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int input;
        cin >> input;
        arr[input]++;
        
    }

    for (int i = 1; i <= 10000; i++) {
        if (arr[i] != 0) {
            for (int j = 1; j <= arr[i]; j++) {
                cout << i << "\n";
            }
        }
    }
}

 

 

다른 정렬방법으로 나중에 풀어봐야겠다.

'[백준] > C++' 카테고리의 다른 글

백준 9252번 LCS 2 [C++]  (0) 2023.09.03
백준 1260번 DFS와BFS [C++]  (0) 2023.08.30
백준 11866번 요세푸스 문제 0 [C++]  (0) 2023.08.04
백준 2751번 수 정렬하기 2 [C++]  (0) 2023.08.04
백준 2003번 수들의 합 2 [C++]  (0) 2023.08.03

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

 

11866번: 요세푸스 문제 0

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

www.acmicpc.net

문제 간단 정리

원으로 앉아있고 K번째마다 제거되기 때문에 K 번째가 아닐때는 제외하고 큐를 사용하여 뒤를 넘겨주면 

구현이 가능할테지만... 큐를 사용하지 않고 풀었다, 큐를 사용해서 푼 블로그 참조 https://cocoon1787.tistory.com/234

 

하지만 나는 그냥 큐 사용을 안하고 구현될 것 같아서 다르게 풀었다.

문제 해결 방법

대략 내가 직접 하나하나 세가면서 한다 생각하고 구현하였다.

수를 제거함을 알기위해서 count 변수, 지금 가리키고 있는 수인 포인터 index 변수

수가 제거되었는지 체크하기 위해서 bool 변수 flag를 설정해 두었다.

flag가 false라면 count++(그 수를 지나감을 의미) ,

count가 K(번째 수)가 되었다면 그 수를 제외하고(flag를 true로) 정답에 넣기

정답의 수가 총 N의 개수와 같아진다면 break;

만일 index가 범위를 벗어났다면 1로 초기화

전체 코드

#include<vector>
#include <iostream>
using namespace std;


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

    int N, K;
    cin >> N >> K;

    int index = 1, count = 0;
    bool flag[1001] = { 0, };
    vector<int> ans;

    while (1) {


        if (flag[index] == false) {
            
            count++;

            if (count == K) {
                ans.push_back(index);
                flag[index] = true;
                count = 0;
            }
        }

        if (ans.size() == N) {
            break;
        }

        index++;
        if (index > N) {
            index = 1;
        }

        //cout << "index:" << index << "\n";
    }

    cout << "<";
    for (int i = 0; i < ans.size(); i++) {
        if (i == ans.size() - 1) {
            cout << ans[i] << ">";

        }else cout << ans[i] << ", ";


    }

}

 

문제 간단 정리

정렬문제 아마도 내장함수를 사용하지 않는다면 n logN의 시간복잡도를 갖는 정렬로 풀어야한다.

문제 해결 방법

sort 내장함수 사용 ><

전체 코드

#include<vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

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

    vector<int> vec;
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        vec.push_back(input);
    }
    sort(vec.begin(), vec.end());

    for (int a : vec) {
        cout << a << "\n";
    }
}

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

 

2003번: 수들의 합 2

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net

문제 간단 정리

 

문제 해결 방법

https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-14246%EB%B2%88-K%EB%B3%B4%EB%8B%A4-%ED%81%B0-%EA%B5%AC%EA%B0%84-C 참고

전체 코드

#include<vector>
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll N, M;
    vector<ll> cnt;
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        ll input;
        cin >> input;
        cnt.push_back(input);

    }
    cnt.push_back(0); //인덱스 때문에 하나 추가



    ll count = 0;
    ll start = 0; ll end=0;
    ll sum = cnt[start];

    while (1) {

        if (sum > M) { //합이 클때

            sum -= cnt[start];

            if (start == end) {
                end++;
                sum += cnt[end];
            }
            start++;

        }
        else if (sum < M) { //합이 적을때

            end++;
            sum += cnt[end];
            
        }
        else if (sum == M) {
            count++;
            sum += cnt[++end];
        }
        if (end == N) break;

    }

    cout << count;
}

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

 

14246번: K보다 큰 구간

$n$개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 $[i,j]$ ($i≤j)$의 합이 $k$보다 큰 모든 쌍 $(i, j)$의 개수를 출력하시오.

www.acmicpc.net

문제 간단 정리

구간합으로도 될 것 같다. 하지만 투 포인터로 풀어보자 

만약 12345 이고 K가 5일때

현재 123을 합한상태라면 4 5 는 더할 필요 없이 +3만 해주면 된다. 

이를 유의해서 풀

문제 해결 방법

투 포인터를 이용해서 풀어보자..

인덱스를 조심해야된다

전체 코드

#include<vector>
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll N, M;
    vector<ll> cnt;
    cin >> N ;

    for (int i = 0; i < N; i++) {
        ll input;
        cin >> input;
        cnt.push_back(input);

    }
    cnt.push_back(0); //인덱스 때문에 하나 추가

    cin >> M;


    ll count = 0;
    ll start = 0; ll end=0;
    ll sum = cnt[start];

    while (1) {

        if (sum > M) { //합이 클때

            sum -= cnt[start];
            count += N - end;

            
            if (start == end) {
                end++;
                sum += cnt[end];
            }
            start++;

        }
        else if (sum <= M) { //합이 적을때

            end++;
            sum += cnt[end];
            
        }
        if (end == N) break;

    }

    cout << count;
}

 

문제 간단 정리

'' 생략

문제 해결 방법

이 문제는 섬과 섬 사이의 연결 관계를 파악해야 하는 그래프 관련 문제입니다. 이를 효율적으로 파악하기 위해 Union-Find 알고리즘을 사용합니다.

Union-Find는 그래프의 연결 요소를 식별하고 관리하기 위한 알고리즘입니다. Union-Find 알고리즘에서 'union' 연산은 두 집합을 하나로 합치고, 'find' 연산은 특정 원소가 어떤 집합에 속하는지를 찾는 데 사용됩니다.

본 문제에서는 다리 하나가 무너져 서로 왕복할 수 없는 섬들이 생겼습니다. 이때 두 섬을 다시 다리로 이어서 모든 섬이 왕복 가능하도록 해야 합니다. 이를 위해 먼저 주어진 섬 간 연결 정보를 이용해 각 섬의 부모 노드 정보를 업데이트합니다. 이렇게 하면 어떤 섬이 어떤 섬과 연결되어 있는지를 빠르게 알 수 있습니다.

Union-Find 알고리즘을 적용한 코드는 다음과 같습니다.

전체 코드

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int parent[1000001];

int getParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}

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

    

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= N - 2; i++) {
        int a, b;
        cin >> a >> b;
        unionParent(a, b);
       
    }
    for (int i2 = 1; i2 <= N - 1; i2++) {
        int A = i2;
        for (int j = i2 + 1; j <= N; j++) {
            int B = j;
            A = getParent(A);
            B = getParent(B);
            if (A != B) {
                cout << A << " " << B;
                return 0;
            }

        }
    }
    

    return 0;

    
}

 

 

문제 간단 정리

구현문제이다

각 블럭들을 돌아가면서 조사하면 되는 간단한 구현문제지만

어떻게 구현하냐에 따라서 시간이 달라질것이다.

나는 그냥 모든 블럭들을 조회하는 무식한 방법으로 풀었다.

이렇게 풀면 오류도 많고 틀릴 가능성이 높으니

아마 각 블럭 모양을 만들고 회전시키는 방법이 가장 바람직하지 않을까 싶다

https://stack07142.tistory.com/299 예시

 

문제 해결 방법

#include<queue>
#include<deque>
#include <iostream>

using namespace std;

int main() {
    int arr[100][100];


    int count = 1;

    while (1) {
        int N; cin >> N;
        if (!N) break;
        //i 세로 j 가로

        int temp = 0;
        int max = -987654321;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> arr[i][j];
            }
        }

        // ㅡ
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - 3; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3];
                if (temp > max) max = temp;
            }
        }
        // ㅣ
        for (int i = 0; i < N - 3; i++) {
            for (int j = 0; j < N; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 3][j];
                if (temp > max) max = temp;
            }
        }

        //ㅓ
        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i + 1][j] + arr[i + 1][j + 1] + arr[i][j + 1] + arr[i + 2][j + 1];
                if (temp > max) max = temp;
            }
        }
        //ㅗ
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i + 1][j] + arr[i + 1][j + 1] + arr[i][j + 1] + arr[i + 1][j + 2];
                if (temp > max) max = temp;
            }
        }
        //ㅜ
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1];
                if (temp > max) max = temp;
            }
        }
        //ㅏ
        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1];
                if (temp > max) max = temp;
            }
        }
        //ㅁ
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1];
                if (temp > max) max = temp;
            }
        }
        //ㅁㅁ
        //  ㅁㅁ
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
                if (temp > max) max = temp;
            }
        }

        //  ㅁ
        //ㅁㅁ
        //ㅁ

        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j+1] + arr[i + 1][j+1] + arr[i + 1][j] + arr[i +2][j];
                if (temp > max) max = temp;
            }
        }



        //ㅁㅁㅁ
        //    ㅁ

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2];
                if (temp > max) max = temp;
            }
        }
        //  ㅁ
        //  ㅁ
        //ㅁㅁ

        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j+1] + arr[i + 2][j];
                if (temp > max) max = temp;
            }
        }

        //ㅁ
        //ㅁㅁㅁ

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
                if (temp > max) max = temp;
            }
        }

        //ㅁㅁ
        //ㅁ
        //ㅁ

        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j + 1] + arr[i][j] + arr[i + 1][j] + arr[i + 2][j];
                if (temp > max) max = temp;
            }
        }

        cout << count << ". " << max << endl;

        count++;
    }
    


    
}

전체 코드

 

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

 

4920번: 테트리스 게임

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 쓰여 있는 숫자가 주어진다. 숫자는 절댓

www.acmicpc.net

 

 

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

 

11687번: 팩토리얼 0의 개수

첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다.

www.acmicpc.net

 

#문제 간단 정리

이하생략

 

#문제 해결 방법

끝의 0의 개수는 2*5의 개수로 정해지고,

2는 2의배수만큼 5는 5의 배수만큼 존재하기 때문에 2가 항상 5보다 많다

때문에 5의 개수만 세주면 0의 개수와 같다

 

이분탐색의 범위는 m*5! 이 무조건 m개의 5의개수보다 많은 5를 가지므로

right를 m*5로 설정해주면 된다.

 

또한 포함된 5의 개수는 5부터 5의제곱수들을 차례대로 나눈 몫을 구하면 5의 개수를 구하는

함수를 만들 수 있다.

 

#전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;


//5가 들어간 개수를 찾는 함수
int findFive(int a) {
    int count = 0;

    for (int i = 5; i <= a; i *= 5) {
        count += (a / i);
    }
    return count;
}

int main() {

    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    //0의 개수는 5의 개수와 동일
    //제곱이 나오는 경우는 숫자가 건너뛰어짐
    int input;
    cin >> input;

    int left = 1;
    int right = input*5;
    int target = input;
    int result = 0;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (findFive(mid) == target) {
            right = mid -1;
        }
        else if (findFive(mid) > target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    
    if (findFive(left) == target) {
        cout << left;
    }
    else {
        cout << -1;
    }
    
    return 0;
}

+ Recent posts