☘️ 20500. Ezreal 여눈부터 가네 ㅈㅈ

문제

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된
$N$자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.

참가자 여러분도 궁금하지요?

안 궁금함? 15ㄱ

입력

 $N$이 주어진다.

출력

문제의 답을
$1\,000\,000\,007$로 나눈 나머지를 출력한다.

제한

$1 \le N \le 1\,515$ 

예제 입력 1

1

예제 출력 1

0

예제 입력 2

2

예제 출력 2

1

예제 입력 3

3

예제 출력 3

1

예제 입력 4

1515

예제 출력 4

939178250

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 정수론

코드 - python3 성공

import sys

input = sys.stdin.readline

# 초기화: dp[i][j]는 i자리 수에서 j로 끝나는 수의 개수
dp = [[0 for _ in range(3)] for _ in range(1516)]

# 1자리 수일 때, 1로 끝나는 수의 개수는 1
dp[1][1] = 1

# Bottom-up 방식으로 동적 계획법 수행
for i in range(2, 1516):
    # i자리 수에서 0으로 끝나는 경우
    dp[i][0] = dp[i - 1][1] + dp[i - 1][2]
    # i자리 수에서 1로 끝나는 경우
    dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
    # i자리 수에서 5로 끝나는 경우
    dp[i][2] = dp[i - 1][0] + dp[i - 1][1]

    # 나머지를 적용하여 값 갱신
    for j in range(3):
        dp[i][j] %= 1000000007

# 입력받은 N에 대한 결과 출력
print(dp[int(input())][0])

---

☘️ 1041. 주사위

문제

    +---+        
    | D |        
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |        
    +---+  

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.

A, B, C, D, E, F에 쓰여 있는 수가 주어진다.

지민이는 현재 동일한 주사위를 N3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.

N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

2
1 2 3 4 5 6

예제 출력 1

36

예제 입력 2

3
1 2 3 4 5 6

예제 출력 2

69

예제 입력 3

1000000
50 50 50 50 50 50

예제 출력 3

250000000000000

예제 입력 4

10
1 1 1 1 50 1

예제 출력 4

500

알고리즘 분류

• 수학
• 그리디 알고리즘

코드 - python3 성공

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
ans = 0
min_lists = []

if N == 1: # 주사위 1개일 때
    arr.sort()
    for i in range(5):
        ans += arr[i]
else:
    # 주사위 여러개인 경우, 마주보는 면 중 작은 값을 선택하여 리스트에 저장
    min_lists.append(min(arr[0], arr[5]))
    min_lists.append(min(arr[1], arr[4]))
    min_lists.append(min(arr[2], arr[3]))
    min_lists.sort()

    # 1, 2, 3개의 면을 보았을 때의 최소값
    min1 = min_lists[0]
    min2 = min_lists[0] + min_lists[1]
    min3 = sum(min_lists)

    # 각 경우에 대한 주사위 개수 계산
    n1 = 4 * (N - 2) * (N - 1) + (N - 2) ** 2
    n2 = 4 * (N - 1) + 4 * (N - 2)
    n3 = 4

    # 최종 정답 계산
    ans += min1 * n1
    ans += min2 * n2
    ans += min3 * n3

# 결과 출력
print(ans)

☘️ 24551. 일이 너무 많아...

문제

카카오에 7년 경력을 가진 신입 개발자로 입사한 pichulia. pichulia 는 카카오 서비스 중 카카오 지갑 서비스 개발 담당자가 되었다.

카카오 지갑은 사용자가 소유한 디지털 자산과 아이템이 담기는 곳으로써 본인 확인을 거쳐 이용할 수 있는 카카오의 다양한 서비스를 모아볼 수 있는 공간이다.

카카오 지갑에서 제공하는 서비스는 매우 다양하다. 우선 '카카오 인증서'를 통해 각종 금융기관과의 연동 서비스를 지원한다. 그리고 '톡명함'을 통해 나를 돋보이게 만드는 명함을 만들 수 있고, 이 명함을 이용해 개발자 커뮤니티 등, 나를 필요로 하는 사람들과 소통할 수 있다. 게다가 '지갑 QR' 을 이용한 무인 매장 이용 서비스도 지원한다. 이 외에도 많은 서비스를 제공하고 있다.

사용자 입장에서는 진짜 지갑처럼 매우 유용하게 사용할 수 있을 것이다. 하지만 개발자 입장에서는 이 모든 것이 정상적으로 돌아가도록 관리를 해야만 하기 때문에 pichulia 는 언제나 일이 많다.

일이 하나만 있는 것도 힘든데, 이렇게 일이 여러 개가 있다... ㅠㅜ

그래서 pichulia 는
$11$,
$111$,
$1111$,
$\cdots$ 와 같이 2개 이상의 숫자
$1$로만 이루어진 수를 싫어한다. 게다가 이러한 수를 약수로 가진 수도 싫어한다.

양의 정수
$N$이 주어졌을 때,
$1$ 이상
$N$ 이하의 정수 중 pichulia 가 싫어하는 수의 개수를 구해보자. pichulia 는 위에 서술된 특징을 가진 정수를 제외한 모든 수를 싫어하지 않는다고 가정한다.

입력

첫 번째 줄에 문제에서 정의된 정수
$N$이 주어진다. (
$1 \le N \le 10^{18}$)

출력

$1$ 이상
$N$ 이하의 정수 중 2개 이상의 숫자
$1$로만 이루어진 수를 약수로 가지는 수의 개수를 출력한다.

예제 입력 1

111

예제 출력 1

11

예제 입력 2

111111111

예제 출력 2

11020111

예제 입력 3

1000000000000000000

예제 출력 3

99180991810801810

알고리즘 분류

• 수학
• 임의 정밀도 / 큰 수 연산
• 포함 배제의 원리

코드 - python3 성공

import sys
input = sys.stdin.readline

# 함수: 최대공약수(Greatest Common Divisor) 계산
def GCD(a, b):
    if b == 0:
        return a
    else:
        return GCD(b, a % b)

# 함수: 최소공배수(Least Common Multiple) 계산
def LCM(a, b):
    return a * b // GCD(a, b)

# 함수: 이진수에서 1의 개수 계산
def count_one(mask):
    cnt = 0
    for i in range(0, 7):
        if mask & (1 << i) != 0:
            cnt += 1
    return cnt

# 함수: 주어진 마스크에 해당하는 최소공배수 계산
def LCMs(mask):
    ret = 1;
    for i in range(0, 7):
        if mask & (2 ** i) != 0:
            ret = LCM(ret, arr[i])
    return ret

# 입력: N 값
N = int(input())

# 주어진 숫자 패턴 : 소수 2, 3, 5, 7, 11, 13, 17
arr = [11, 111, 11111, 1111111, 11111111111, 1111111111111, 11111111111111111]

# 초기값: 결과 변수 ret에 N 대입
ret = N;

# 모든 경우의 수에 대해 반복
for i in range(0, (2 ** 7)):
    # 이진수로 표현했을 때 1의 개수가 짝수이면 빼기, 홀수이면 더하기
    if count_one(i) % 2 == 0:
        ret -= N // LCMs(i)
    else:
        ret += N // LCMs(i)

# 결과 출력
print(ret)

---

☘️ 1368. 물대기

문제

선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.

입력

첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)를 의미한다.

출력

첫 줄에 모든 논에 물을 대는데 필요한 최소비용을 출력한다.

예제 입력 1

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

예제 출력 1

9

알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

코드 - python3 성공

import sys
import heapq

input = sys.stdin.readline

# 입력: 논의 수 N
N = int(input())
node_list = []  # (우물 파는 비용, 논 번호)를 저장하는 힙
pay_list = []   # 각 논의 우물 파는 비용을 저장하는 리스트

# 각 논의 우물 파는 비용을 입력받아 힙과 리스트에 저장
for i in range(N):
    pay = int(input())
    heapq.heappush(node_list, (pay, i))
    pay_list.append(pay)

# 각 논들 사이의 물을 끌어오는 비용을 2차원 리스트로 입력받음
connect_list = [list(map(int, input().split())) for _ in range(N)]

result = 0  # 결과 변수 초기화
visited = [False] * N  # 방문 여부를 저장하는 리스트 초기화

# 우선순위 큐(node_list)가 빌 때까지 반복
while node_list:
    pay, node = heapq.heappop(node_list)
    # 이미 방문한 논이면 스킵
    if visited[node]:
        continue
    visited[node] = True
    result += pay  # 결과에 현재 논의 우물 파는 비용 추가

    # 현재 논과 연결된 모든 논에 대해
    for next_node in range(N):
        if next_node != node:
            # 만약 더 저렴한 비용으로 물을 끌어올 수 있다면 업데이트 후 힙에 추가
            if pay_list[next_node] > connect_list[node][next_node]:
                pay_list[next_node] = connect_list[node][next_node]
                heapq.heappush(node_list, (pay_list[next_node], next_node))

# 결과 출력
print(result)

---

☘️ 9527. 1의 개수 세기

문제

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.

즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

입력

첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 1016)

출력

1의 개수를 세어 출력한다.

예제 입력 1

2 12

예제 출력 1

21

알고리즘 분류

• 수학
• 누적 합
• 비트마스킹

코드 - python3 성공

import sys
input = sys.stdin.readline


def count(num):
    cnt = 0
    # 주어진 숫자를 이진수로 변환하여 저장
    bin_num = bin(num)[2:]
    # 이진수의 길이 구하기
    length = len(bin_num)

    # 이진수를 뒤에서부터 순회하면서 1의 개수 계산
    for i in range(length):
        if bin_num[i] == '1':
            # 현재 자릿수의 2의 거듭제곱 값
            val = length - i - 1
            # 현재 자릿수까지의 1의 개수를 누적
            cnt += one_sum[val]
            # 가장 큰 2의 거듭제곱 수까지의 1의 개수를 더해줌
            cnt += (num - 2 ** val + 1)
            # 다음 자릿수 계산을 위해 현재 자릿수 제외
            num = num - 2 ** val

    # 최종적으로 계산된 1의 개수 반환
    return cnt

# 입력 받기
x, y = map(int, input().split())

# 각 자릿수의 1의 개수를 저장하는 리스트 초기화 (log2(10**16))
one_sum = [0 for _ in range(60)]

# one_sum 리스트 계산
for i in range(1, 60):
    # 현재 자릿수까지의 1의 개수를 계산하기 위해 2의 거듭제곱을 사용, i - 1은 현재 자릿수
    one_sum[i] = 2 ** (i - 1) + 2 * one_sum[i - 1]

# A부터 B까지의 1의 개수 합을 계산하고 출력
print(count(y) - count(x - 1))