척척석사의 코딩기록

문제는 이하와 같습니다.

import sys

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

M = max(maximum)
prime_cnt = [0] * (2*M +1)
num = [0] * (2*M + 1)
num[0] = 1
num[1] = 1
for i in range (2,2*M+1):
    if num[i] == 0:
        prime_cnt[i] = prime_cnt[i-1] + 1
        for j in range (2*i,2*M+1,i):
            num[j] = 1
    else:
        prime_cnt[i] = prime_cnt[i-1]

#Hint: 3개 이상의 연속한 정수의 합은 소수가 될 수 없다.
for i in range (0,N):
    cnt = prime_cnt[2*A[i][1]-1] - prime_cnt[2*A[i][0]]
    print(cnt)

해당 코드의 Hint:

3개 이상의 연속한 자연수를 합한 결과는, 반드시 합성수가 된다는 것에 기인합니다.

n(>2)개의 연속한 자연수를 써보면

k, k+1, k+2, ... , k +(n-1)로 주어지고, 이들의 합은 kn + (n(n-1)/2) 꼴로 나타낼 수 있습니다.

자연스럽게 n을 공통 인수로 갖고있고, n(k + (n-1)/2) 로 나타낼 수 있습니다.

만약 n이 홀수라면 (n-1)/2의 부분은 자연스럽게 정수가 되고, n의 배수, 즉 합성수가 되겠습니다.

한편 n이 짝수라면 n = 2m으로 쓸 수 있으므로
2m(k + (2m-1)/2) = m(2k + 2m - 1) 로 쓸 수 있겠습니다. 각각 m과 2k + 2m -1 은 정수입니다.

여기서 n이 3이상이라고 하였으므로, m은 2 이상의 자연수가 될 것이고 m(2k + 2m -1)은 m의 배수가 되면서, 합성수가 되겠습니다.

즉 가능한 것은 연속한 두 수의 합으로 나타낼 수 있는 소수 이며,
이것들의 counting을 얼마나 빠르게 구현할 수 있는가가 이 문제의 해결방법이 되겠습니다.

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

if int(math.sqrt(N)) - math.sqrt(N) == 0:
    print(-1)
else:
    cnt1 = 0
    #N이 빗변인 경우
    for i in range (1,int(math.sqrt(N/2))+1):
        j = N - i**2
        #j가 어떤 정수의 제곱꼴인지 판단하는 방법#
        if math.sqrt(j) - int(math.sqrt(j)) == 0:
            cnt1 += 1
        else:
            continue
    #N이 빗변이 아닐 경우
    #N = B ** 2 - A ** 2 = (B+A)(B-A)로 계산된다. 두 수의 기우성이 동일해야함.
    cnt2 = 0
    for i in range (1,int(math.sqrt(N))+1):
        if N % i == 0:
            if (i + (N // i)) % 2 == 0:
                if i == N // i:
                    continue
                else:
                    cnt2 += 1
        else:
            continue

    print(cnt1 + cnt2)

문제는 이렇게 주어졌습니다.

즉, 원점을 통과하는 직선이 주어진 points을 얼마나 많이 통과하는가? 에 대한 내용이 되겠습니다.

import sys
input = sys.stdin.readline

N = int(input())
dict = {}
A = []
for i in range (0,N):
    a,b = map(int,input().split())
    c = math.gcd(a,b)
    a //= c
    b //= c
    if (a,b) not in dict:
        dict[(a,b)] = 1
    else:
        dict[(a,b)] += 1


print(max(dict.values()))

해설)

제가 작성한 코드 위와 같습니다.
사용한 아이디어는 Projection (사영) 입니다.

예를 들어보겠습니다.
(100,200) 라는 점이 주어져있을 때, x좌표와 y좌표의 최대공약수는 100입니다.
두 좌표를 최대공약수로 나눠주면 새로운 좌표는 (1,2)가 되겠습니다.

이렇게 얻어진 (1,2)라는 새로운 좌표는 x좌표와 y좌표가 서로소임을 알 수 있습니다.

같은 방법으로, (1024,2048)이라는 점이 주어졌다면
최대공약수 1024로 x,y좌표를 나누어 새로운 좌표 (1,2)를 얻습니다.

이제 이것들을 딕셔너리에 넣어주겠습니다.
만약 (1,2)라는 새로운 좌표가 딕셔너리 안에 존재하고있다면,
그것의 value 값을 하나 늘려주고,
만약 딕셔너리 안에 없다면, 새로운 key (1,2) - value = 1를 추가해주면 되겠습니다.

그리고 키 값 중 최대치를 출력해주면 되겠습니다.

#29733
R,C,H= map(int,input().split())
box = []
for i in range (0,H):
    box_lev = []
    for j in range (0,R):
        a = list(input())
        box_lev.append(a)
    box.append(box_lev)

ans = [[[0 for _ in range (0,C)] for _ in range (0,R)] for _ in range (0,H)]
for i in range (0,H):
    for j in range (0,R):
        for k in range (0,C):
            if box[i][j][k] == "*":
                ans[i][j][k] = "*"
            else:
                cnt = 0
                for a in (-1,0,1):
                    for b in (-1,0,1):
                        for c in (-1,0,1):
                            x = i + a
                            y = j + b
                            z = k + c
                            if 0 <= x < H and 0 <= y < R and 0 <= z < C:
                                if box[x][y][z] == "*":
                                    cnt += 1
                ans[i][j][k] = cnt % 10

result = []
for i in range (0,H):
    for j in range (0,R):
        z = "".join(str(t) for t in ans[i][j])
        result.append(z)

for a in result:
    print(a)

import math
def f(x):
    if x == 1:
        return 1
    elif x == 2:
        return 2
    else:
        a = int(math.sqrt(x))
        b = int(math.sqrt(x)) + 1
        if math.sqrt(x) - a == 0:
            return 2*a -1 
        else:
            if a**2 + 1 <= x < ((a ** 2 + 1) + b ** 2)/2 :
                return 2*a
            else:
                return 2*a + 1
            
N = int(input())
ans = []
for i in range (0,N):
    a,b = map(int,input().split())
    ans.append(f(b-a))
for i in range (0,N):
    print(ans[i])

힌트는 아래와 같다.

1 = 1 :1
2 = 1+1 :2
3 = 1+1+1 :3
4 = 1+2+1 :3
5 = 1+2+1+1 :4
6 = 1+2+2+1 :4
7 = 1+2+2+1+1 :5
8 = 1+2+2+2+1 :5
9 = 1+2+3+2+1 :5
10 = 1+2+3+2+1+1 :6
11 = 1+2+3+2+2+1 :6
12 = 1+2+3+3+2+1 :6
13 = 1+2+3+3+2+1+1 :7
14 = 1+2+3+3+2+2+1 :7
15 = 1+2+3+3+3+2+1 :7
16 = 1+2+3+4+3+2+1 :7
17 = 1+2+3+4+3+2+1+1 :8
18 = 1+2+3+4+3+2+2+1 :8
19 = 1+2+3+4+3+3+2+1 :8
20 = 1+2+3+4+4+3+2+1 :8
21 = 1+2+3+4+4+3+2+1+1 :9
22 = 1+2+3+4+4+3+2+2+1 :9
23 = 1+2+3+4+4+3+3+2+1 :9
24 = 1+2+3+4+4+4+3+2+1 :9
25 = 1+2+3+4+5+4+3+2+1 :9

규칙이 생기는 지점이 제곱수와 제곱수 사이 (ex:9,16,25) 인것에 착목하면 좋을 것 같다 :)

대충, 이렇게 이루어진 트리가 있을때 주어진 튜플이 몇번째 튜플인지 맞춰보세요

라는 문제입니다.

아이디어는 굉장히 간단한데 중간 과정에서 제가 현명하지 못하게 코드를 짠 것 같습니다.

import math
N = []
graph = []
while True:
    a = input()
    if a == "-1":
        break
    else:
        x = list(a)
        B = []
        y = [False for _ in range (0,len(x))]
        
        for i in range (0,len(x)):
            if x[i] == "(" or x[i] == ")" or x[i] == ",":
                continue
            else:
                if y[i] == False:
                    c = []
                    j = i
                    while x[j] != "(" and x[j] != ")" and x[j] != ",":
                        c.append(x[j])
                        j += 1
                        y[j] = True
                    s = "".join(str(t) for t in c)
                    B.append(s)
                else:
                    continue
        n = int(B[0])
        route = B
        route.remove(route[0])
        N.append(n)
        graph.append(route)
A = []
for i in range (0,len(N)):
    num = []
    summary = 0
    for j in range (0,N[i]):
        num.append(j+1)
    for k in range (1,N[i]+1):
        summary += math.factorial(N[i] - k) * (num.index(int(graph[i][k-1])))
        num.remove(int(graph[i][k-1]))
    A.append(summary + 1)

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

소스코드가 조금 더럽네요.

솔직히 다른것보다 주어진 튜플에서 숫자 추출해내는게 제일 어려웠습니다 ...

결국 False로 이루어진 리스트 생성해서 중복체킹 안되게끔 ....

수많은 밸류 에러들을 뚫고 한문제 다시 치워버렸습니다

import sys
import math
from itertools import permutations
from itertools import combinations

N,M = map(int,input().split())
symbol = list(input().split())
sym1 = []
sym2 = []
dic = ["a","e","i","o","u"]
for sym in symbol:
    if sym in dic:
        sym1.append(sym)
    else:
        sym2.append(sym)

pw = []
for comb in combinations(symbol,N):
    cnt1 = 0
    cnt2 = 0
    for x in comb:
        if x in sym1:
            cnt1 += 1
        else:
            continue
    for x in comb:
        if x in sym2:
            cnt2 += 1
        else:
            continue
    if 1 <= cnt1 and 2 <= cnt2:
        comb = list(comb)
        comb.sort()
        s = "".join(t for t in comb)
        pw.append(s)
    else:
        continue
    
pw = list(set(pw))
pw.sort()
for _ in pw:
    print(_)

주어진 단어에 대하여 모음 / 자음으로 분리 후
combination으로 먼저 N자리의 password를 추출해냅니다.

그리고 password에서 자음의 갯수와 모음의 갯수에 대한 조건을 만족하는지 확인 하는 작업 (for x in comb 부분)

그리고 조건을 만족하는 password에 대하여 이를 이어주면 되겠습니다.
(중복되는 password는 생략시켜주기)

#1612 가지고 노는 1
import sys

input = sys.stdin.readline
N = int(input())
if N == 1:
    print(1)
elif N % 2 == 0 or N % 5 == 0:
    print(-1)
else:
    x = 1
    time = 1
    while x != 0:
        x += (9*x + 1) % N
        x = x % N
        time += 1
    print(time)

10^n을 계속해서 더하면 되는 것이므로,
1 -> (9 x 1 + 1) + 1 = 11 - > (11 x 9 + 1) + 11 = 111 -> ... 꼴로 나타내어줄 수 있다.

항상 N으로 나누어주면서 큰 수가 나오지 않도록 막아주는것이 중요한 포인트가 되겠다.