척척석사의 코딩기록

#3944 나머지계산
import sys

input = sys.stdin.readline
N = int(input())
A = []
for i in range (0,N):
    a,b = input().split()
    a = int(a)
    A.append([a,b])

for i in range (0,N):
    result = 0
    for j in range (0,len(A[i][1])):
        result += int(A[i][1][j]) % (A[i][0]-1)

    result %= (A[i][0]-1)

    print(result)

Pypy로는 시간내로 나오는데 Python으로는 잘 안 나와서 슬픈 상황.

아이디어로는, b진법 수를 10진법으로 변환시켜서 생각하고,
그것을 b-1로 나눈 나머지를 구하는 것이므로
각 자릿수의 합을 구한 뒤 b-1로 나누어 달라는 것과 다를 것이 없다.

예를 들어,
888이 9진법으로 나타내어져있을때, 이를 10진법으로 나타낸다면 8$9^2$ + 8$9$ + 8인데

이를 8 $9-1$로 나눈 나머지를 구한다면
윗 식의 각 항에 대하여 8로 나눈 나머지가 되므로 8$1^2$ + 8$1$ + 8 = 24 를 8로 나눈 나머지 0이 나오게 되는 것이다.

#2981 검문

import sys
import math

input = sys.stdin.readline
N = int(input())
A = []
for i in range (0,N):
    a = int(input())
    A.append(a)

A = list(set(A))
B = []
 
for i in range (0,len(A)-1):
    for j in range (i+1,len(A)):
        b = A[j] - A[i]
        B.append(b)

gcd = B[0]
for i in range (1,len(B)):
    gcd = math.gcd(gcd,B[i])

gcd = math.fabs(gcd)
result = []
for i in range (1,int(math.sqrt(gcd))+1):
    if gcd % i == 0:
        result.append(i)
        c = int(gcd // i)
        result.append(c)
    else:
        continue
result = list(set(result)) 
result.remove(1)
result.sort()

s = " ".join(str(t) for t in result)
print(s)

이전 포스팅과 크게 다른 것이 없었던 문제인데,
이 문제는 gcd의 약수까지 전부 구해달라고 하는것이 하나의 함정.

코딩을 하면서 런타임에러 $ValueError$가 자주 떴는데,
그 이유는 gcd의 값이 음수가 나오면서 for i in range $1,-----$ 의 부분에서 math.sqrt$gcd$에서 에러가 떴는데, gcd에 절댓값을 취하게 해줌으로서 해결 가능.

시간은 52ms로 아주 나이스하게.

#1684 같은 나머지

import sys
import math

input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
#혹시 모를 중복을 미리 set을 사용하여 제거#
A = list(set(A))
B = []
 
for i in range (0,len(A)-1):
    for j in range (i+1,len(A)):
        b = A[j] - A[i]
        B.append(b)
gcd = B[0]
for i in range (1,len(B)):
    gcd = math.gcd(gcd,B[i])

print(gcd)

#1016 제곱 ㄴㄴ수

import sys
import math


A,B = map(int,input().split())
C = int(math.sqrt(B))
nest = [1] * (B-A+1)

for i in range (2,C+1):
    a = A // (i ** 2)
    a *= (i ** 2)
    if a * (i ** 2) <  A and B < (a + 1) * (i ** 2):
        continue
    else:
        for j in range (a,B + 1,(i ** 2)):
            if j - A >= 0:
                nest[j-A] = 0

print(nest.count(1))

이것도 좀 나중에 설명을 좀 써둬야겠네요 ㅋㅋ ㅠ 

#1463 1로 만들기
import sys
import math

input = sys.stdin.readline
N = int(input())

#0,1,2,3으로부터 최단거리로 1을 만드는 방법#
dp = [0,0,1,1]
for x in range (4,N+1):
    if x % 2 != 0 and x % 3 != 0:
        y = dp[x-1] + 1
        dp.append(y)
    elif x % 2 != 0 and x % 3 == 0:
        y = min(dp[x//3],dp[x-1]) + 1
        dp.append(y)
    elif x % 2 == 0 and x % 3 != 0:
        y = min(dp[x//2],dp[x-1]) + 1
        dp.append(y)
    else:
        y = min(dp[x//2],dp[x//3],dp[x-1]) + 1
        dp.append(y)

print(dp[N])

귀여운 dp 문제였나봅니다.

#1790번 수 이어쓰기 2
import sys
import math
input = sys.stdin.readline

N,k = map(int,input().split())

a = len(str(N))
length_N = 0

#출력 가능인가 판정#
if a == 1:
    length_N += N
else:
    for i in range (1,a+1):
        length_N += 9 * (10 ** (i-1)) * i
    length_N += (N - (10 ** a) + 1) * a

#몇번째 digit에 포함되는지 확인
digit = 1
length = 1
while True:
    if length <= k and k < length + 9 * digit * (10 ** (digit-1)) :
        break
    else:
        length += 9 * digit * (10 ** (digit-1))
        digit += 1
#판정 후 계산#
if k <= length_N:
    for i in range (1,digit):
        k -= 9 * (10 ** (i-1)) * i
    m = 0
    while True:
        if m * digit + 1 <= k and k <= (m + 1) * digit:
            break
        else:
            m += 1
    b = k % digit
    c = 10 ** (digit-1) + (m)
    print(str(c)[b-1])

else:
    print(-1)

Pypy로 풀었네요. 파이썬으로는 실행시간에 부족한게 있었나봅니다.

#2877번 4와 7
import sys
import math
input = sys.stdin.readline

N = int(input())

digit = 1
word = []
while True:
    if 2**(digit) - 1 <= N and N <= 2**(digit+1) - 2:
        break
    else:
        digit += 1

while digit != 0:
    if 2**(digit) - 1 <= N and N <= 2**(digit) -2 + (2**(digit - 1)):
        word.append("4")
        N -= 2**(digit - 1)
        digit -= 1
        
    else:
        word.append("7")
        N -= 2**digit
        digit -= 1
  
result =  "".join(str(s) for s in word)
print(result)

블로그를 옮기고 있는데 원본 작성할 때 뭔가 써둔 말이 없네요?

좀 있다가 한번 읽어봐야겠습니다. 

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
target = int(input())
A.sort()

cnt = 0
if min(A) <= target:
    for i in range (0,N-1):
        if A[i] < target and target < A[i+1]:
            for x in range (A[i]+1,A[i+1]-1):
                for y in range (x+1,A[i+1]):
                    if x <= target and target <= y:
                       cnt += 1
                    else:
                       continue
        else:
            continue
else:
    for x in range (1,min(A)-1):
        for y in range (x+1,min(A)):
            if x <= target and target <= y:
                cnt += 1
            else:
                continue

print(cnt)

아이디어로는, 처음에 먼저 집합 S의 갯수를 받은 뒤, 그에 따라 S의 각 원소를 받습니다.
그 뒤, 찾고자 하는 target의 위치를 받아주겠습니다. $문제의 setting$

제일 중요한 것은,이 집합 S의 minimum과 target의 대소관계입니다.
$아마 문제에서, 1<= n <= max(S$로 준 것은 이런 부분에서의 제약이 되겠습니다.)

케이스를 나눠서

I) S의 minimum 값이 target보다 작다면, target은 S의 각 원소 사이사이에 존재하고 있는 상황
II) S의 minimum 값이 target보다 크다면, target은 1과 min$S$사이에 존재하고 있는 상황

I) S의 어떤 원소와 원소 사이에 존재하는지 그 값들을 찾은 뒤, 그 안에서의 좋은 구간 탐색을 진쟁

II) 바로 좋은 구간 탐색을 진행

이렇게 해주면 되겠습니다.