졍's 기술 블로그

약수

티어 : Bronze 1
알고리즘 분류 : 수학, 정수론

약수 짝끼리의 곱은 N이 된다는 성질을 이용했다.

e.g., 8의 약수 = {1, 2, 4, 8}

         → 1 * 8 = 8

         → 2 * 4 = 8

따라서 진짜 약수를 모두 벡터에 담은 후 벡터를 오름차순 정렬하면 벡터의 첫 번째 요소와 마지막 요소는 약수 짝이 될 것이므로 두 값을 곱한 값이 N이 된다.

Algorithm

1. 입력받은 진짜 약수를 모두 vector에 담음
2. 벡터를 오름차순 정렬해 약수끼리 짝이 맞을 수 있도록 함
3. 벡터의 첫 번째 요소와 마지막 요소를 곱함

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt; // N의 진짜 약수의 개수
vector <int> v; // N의 진짜 약수
int N;

void input(){
    cin >> cnt;
    for(int i=0;i<cnt;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
}

void solution(){
    // 벡터 오름차순 정렬
    sort(v.begin(), v.end());
    // 벡터의 처음 값과 마지막 값 곱함
    N = v[0] * v[v.size()-1];
}

void output(){
    cout << N;
}

int main(void){
    input();
    solution();
    output();
    return 0;
}

메모리: 2020 KB
시간: 0 ms

1

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

예제 입출력

우선 알고리즘은 각 자릿수가 1로 이루어진 숫자로 n이 나누어 떨어질 때까지 확인하는 방식을 이용했다.

처음에는 각 자릿수가 1로 이루어진 숫자를 만들기 위해 문자열을 이용했다.

num이라는 string형 변수를 하나 만들어 n으로 나누어떨어지지 않으면 '1'을 추가해주는 방식으로 아래와 같이 구현했다.

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

int cal_len(long long n){
    string num = to_string(n);
    return num.length();
}

long long ispossible(int n){
    // n의 길이 계산
    int len = cal_len(n);
    string num;
    // n의 길이만큼 1로만 구성된 문자열 만들기
    for(int i=0;i<len;i++){
        num += '1'; // O(n)으로 동작
    }
 
    while(true){
        // num이 n의 배수인지 확인
        if(num%n==0) return num.length();
        // num 한 자리 추가
        num += '1';
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

하지만 런타임 에러(out_of_range)로 실패 ㅠ

num += '1';의 연산이 O(n)으로 동작하기 때문에 연산량이 너무 많기 때문이다.

그래서 num 변수를 long long형으로 선언해 동일한 알고리즘을 사용했다.

#include <iostream>
using namespace std;

long long ispossible(int n){
    int cnt=1;
    long long num=1;
 
    while(true){
        // num이 n의 배수인지 확인
        if(!(num%n)) return cnt;
        
        // num 한 자리 추가
        num = num*10+1;
        cnt++;
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

하지만 이 방법도 동일하게 런타임 에러(out_of_range)가 났다.

결과적으로 런타임 에러의 원인은 num이 너무 커지는 것이었는데, num을 줄이기 위해 Moduler(%) 연산을 이용했다.

Algorithm

Brute Force
1. num(long long형)에 1로 이루어진 숫자를 하나씩 담음
2. num이 n으로 나누어 떨어지는지 확인
    2-1. 나누어떨어지면 num의 길이 return
    2-2. 나누어떨어지지 않으면 num의 길이 증가 (num = num*10 + 1 연산)
            → 이 때 moduler 연산(num%=n)을 이용해 num의 크기 줄여주는 것이 이 문제의 핵심 !

Code

#include <iostream>
using namespace std;

long long ispossible(int n){
    int cnt=1;
    long long num=1;
 
    while(true){
        // num이 n의 배수인지 확인
        if(!(num%n)) return cnt;
        
        // num의 크기 줄여주기
        num%=n;
        
        // num 한 자리 추가
        num = num*10+1;
        cnt++;
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // cin.eof(): EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

메모리: 2020 KB
시간: 0 ms

나머지

티어 : Bronze 5
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 구현, 사칙연산

문제

(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?

(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?

세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

출력

첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.

예제 입출력

Code

#include <iostream>
using namespace std;

int main(void){
    int A, B, C;
    cin >> A >> B >> C;
    cout << (A+B)%C << "\n";
    cout << ((A%C)+(B%C))%C << "\n";
    cout << (A*B)%C << "\n";
    cout << ((A%C)*(B%C)%C) << "\n";
    return 0;
}

메모리: 2020 KB
시간: 0 ms

경로 찾기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 플로이드-워셜

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입출력

Algorithm

DFS
1. 그래프 구현
2. DFS 돌면서 갈 수 있는 곳 리스트에 저장
3. 리스트에 들어있는 곳에 맞게 1로 변경

Code

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(x):
    global idx
    # 현재 노드에 방문한 적 있는지 확인
    if visited[x]:
        return False
    
    # 방문 기록
    # dfs를 첫 번째 수행하는 경우가 아닐 때만 수행
    if x != idx or (nodes and x == idx):
        visited[x] = True
        nodes.append(x)
    
    # 인접 노드 방문
    for next_node in graph[x]:
        dfs(next_node)
    
    return True

def set_answer(i):
    for j in nodes:
        answer[i][j] = 1
        
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
answer = [[0 for _ in range(N)] for __ in range(N)]
# 그래프 구현
graph = [[] for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1:
            graph[i].append(j)

# 모든 정점 DFS 돌기
for idx in range(N):
    nodes = []
    visited = [False for _ in range(N+1)]
    
    if dfs(idx):
        # set answer
        set_answer(idx)

for i in range(N):
    print(' '.join(map(str, answer[i])))

메모리: 30840 KB
시간: 92 ms

행렬

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 그리디 알고리즘

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

예제 입출력

Algorithm

구현 - Simulation
1. 다른 숫자인 곳을 왼쪽 위 지점으로 잡고 연산
2. 모두 변환 후 A와 B가 동일한지 비교

Code

# [x][y]의 위치의 값이 같은지 다른지 확인
def is_same(x, y):
    if A[x][y] != B[x][y]:
        return False
    else:
        return True

# [x][y]의 위치의 값을 변경
def change(x, y):
    # [x][y]부터 3x3이 범위를 벗어나면 for문 들어가지 않음
    if x+3 > N or y+3 > M:
        return False
    
    for xx in range(x, x+3):
        for yy in range(y, y+3):
            # 0이면 1로 변경
            if A[xx][yy] == 0:
                A[xx][yy] = 1
            else:
                A[xx][yy] = 0
    return True

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = [list(map(int, input().rstrip())) for _ in range(N)]
B = [list(map(int, input().rstrip())) for _ in range(N)]

answer = 0
for x in range(N):
    for y in range(M):
        # 다른 숫자인 곳이 있으면
        if not is_same(x, y):
            # 해당 위치부터 3x3 만큼 연산
            if change(x, y):
                answer += 1

# A와 B가 같으면 answer 출력
if A==B:
    print(answer)
# 같지 않으면 -1 출력
else:
    print(-1)

메모리: 30840 KB
시간: 76 ms

카드 합체 놀이

티어 : Silver 1
시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 자료 구조, 그리디 알고리즘, 우선순위 큐

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입출력

Algorithm

구현
1. 숫자 오름차순
2. 가장 맨 앞 두 숫자 더한 값으로 대체
3. 1과 2를 m번 반복

Code

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cards = list(map(int, input().split()))

for count in range(m):
    # 숫자 오름차순
    cards.sort()
    cards[0], cards[1] = cards[0]+cards[1], cards[0]+cards[1]

print(sum(cards))

메모리: 30840 KB
시간: 240 ms

영역 구하기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

예제 입출력

Algorithm

DFS
1. 입력받은 꼭지점을 기준으로 사각형의 값 1로 채움
2. DFS를 통해 0인 공간의 개수와 넓이 구하기

Code

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(x, y):
    global count

    # graph 밖으로 벗어나거나 1이면 False 반환
    if x < 0 or y > M-1 or y < 0 or x > N-1:
        return False
    
    # 이미 방문한 곳이면 False 반환
    if visited[x][y] or graph[x][y] == 1:
        return False
    
    # 방문 기록
    visited[x][y] = True
    # 칸 수 세기
    count += 1
    
    # 인접 노드로 이동
    dfs(x-1, y)
    dfs(x+1, y)
    dfs(x, y-1)
    dfs(x, y+1)
    
    return True

M, N, K = map(int, input().split())
inputs = [list(map(int, input().split())) for _ in range(K)]

# 입력받은 좌표를 기준으로 사격형의 값을 1로 채움
graph = [[0 for yy in range(M)] for xx in range(N)]
visited = [[False for yy in range(M)] for xx in range(N)]
for x1, y1, x2, y2 in inputs:
    for x in range(x1, x2):
        for y in range(y1, y2):
            graph[x][y] = 1

# DFS 이용해 0인 공간의 개수와 넓이 구하기
answer = [0]
for x in range(N):
    for y in range(M):
        count = 0
        if dfs(x, y):
            answer[0] += 1
            if count != 0:
                answer.append(count)

print(answer[0])
answer = answer[1:]
answer.sort()
print(' '.join(map(str, answer)))

메모리: 40684 KB
시간: 88 ms

마인크래프트

티어 : Silver 2
시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 1024 MB
알고리즘 분류 : 구현, 브루트포스 알고리즘

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

입력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

예제 입출력

Algorithm

구현
1. 기준 높이보다 높은 블럭의 차이 모두 합하기
2. 기준 높이보다 낮은 블럭의 차이 모두 합하기
3. 기준 높이만큼 쌓을 수 있는 블럭이 존재하면 answer 갱신

Code

import sys
input = sys.stdin.readline

N, M, B = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

max_height = 0
min_height = 256
for x in range(len(graph)):
    for y in graph[x]:
        max_height = max(max_height, y)
        min_height = min(min_height, y)

answer = [(256*2+256)*M*N, max_height]
height = max_height
while height >= min_height:
    # 기준 높이보다 높은 블럭의 차이 모두 합하기
    # 기준 높이보다 낮은 블럭의 차이 모두 합하기
    tall = 0
    short = 0
    for x in range(len(graph)):
        for y in range(len(graph[x])):
            if graph[x][y] > height:
                tall += (graph[x][y] - height)
            elif graph[x][y] < height:
                short += (height - graph[x][y])

    # 기준 높이만큼 쌓을 수 있는 블록이 충분히 존재하면 answer 갱신
    if (B+tall) >= short:
        if answer[0] > tall * 2 + short:
            answer = [tall * 2 + short, height]
    
    # 기준 높이를 낮춰 재검사
    height -= 1
        
print(answer[0], answer[1])

메모리: 117584 KB
시간: 900 ms