척척석사의 코딩기록

N = int(input())
A = []
for i in range (0,N):
    a = list(map(int,input().split()))
    A.append(a)

def f(n):
    if n == 0:
        return A[0][0]
    else:
        for i in range (1,n):
            for j in range (0,len(A[i])):
                if j == 0:
                    A[i][j] += A[i-1][j]
                elif j == len(A[i-1]):
                    A[i][j] += A[i-1][j-1]
                else:
                    a = A[i][j] + A[i-1][j-1]
                    b = A[i][j] + A[i-1][j]
                    A[i][j] = max(a,b)
        ans = max(A[n-1])
        return ans
print(f(N))

먼저, 삼각형의 끝부분의 합에 있어서 좀 더 세밀한 컨트롤이 필요하여, 

else 부분에서의 두번째 for문에서 분기를 넣었습니다.  (j == 0 or j == len(A[i-1]) or the others)

아이디어는 i번째 줄(리스트)의 연산을 할 때, i-1번째 리스트의 길이와 같게 해준다는 것입니다.

그리디 방법으로 풀었어요.

첫번째 연산에서는

그냥 자기 자신만 보면 됩니다. 끝

두번째 연산에서는 

첫번째 줄이 [a11], 두번째 리스트에서 [a21,a22]로 주어졌다고 할 때

두번째 리스트는 [a11 + a21, a11 + a22] 로 만들어줍니다.

세번째 연산에서는

두번째 리스트의 결과 [a11 + a21, a11 + a22]를 사용하여 세번째 리스트 [a31,a32,a33]과 연산을 실행합니다.

첫번째 원소의 경우 : a11 + a21 + a31 

두번째 원소의 경우 : a11 + a21 + a32, a11 + a22 + a32 중 큰 것 b

세번째 원소의 경우 : a11 + a22 + a33

-> [a11 + a21 + a31, b , a11 + a22 + a33] 이렇게 만들어줍니다.

네번째에도 동일한 방법으로,

[a11 + a21 + a31, b , a11 + a22 + a33] 과 [a41,a42,a43,a44]의 경우

첫번째 원소 : a11 + a21 + a31 + a41

두번째 원소 : a11 + a21 + a31 + a42, b + a42 중 큰 것

세번째 원소 : b + a43, a11 + a22 + a33 + a43 중 큰 것

네번째 원소 : a11 + a22 + a33 + a44 

이렇게 귀납적으로 구할 수 있겠고, 마지막 줄에서 가장 큰 원소를 return 해주면 됩니다.

프로그래머스에도 있는 문제더라고요. 레벨3이었나?

이번에도 C까지만 풀고 쉬러 다녀왔습니다.

어제 인적성 검사만 두개를 보고왔어서 상당히 피곤했었네요.

결론적으로 x부터 시작하는 길이 M의 half-open interval에 몇개의 선물이 들어있는지 물어보는 문제입니다. 

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
A = list(map(int,input().split()))
dict = {}
for i in range (0,N):
    if A[i] in dict:
        dict[A[i]] += 1
    else:
        dict[A[i]] = 1
A = list(set(A))
A.sort()
answer = []

if len(A) == 1:
    print(dict[A[0]])
else:
    ans = []
    i = 0
    j = 0
    cnt = 0
    while True:
        if A[j] - A[i] < M:
            cnt += dict[A[j]]
            j += 1
        else:
            cnt -= dict[A[i]]
            i += 1
        if j == len(A) or i == len(A):
            ans.append(cnt)
            break
        else:
            ans.append(cnt)
            continue
    print(max(ans))

아이디어로서는 

먼저 선물의 좌표를 받은 뒤, key를 좌표, value를 선물의 갯수로 해서 딕셔너리를 만들었어요.

그리고 중요한 부분으로, 좌표를 크기순으로 정렬합니다.

그 뒤, 투포인터 + 슬라이딩 형태로 길이 조절을 해가면서 길이의 최댓값을 구했습니다.

(위에서 받은 value값을 추가하거나 빼거나 하는 등)

몇번이나 에러가 나서 왜 그러지? 싶었는데 if len(A) == 1 부분에서 한 점에 다수가 나올 수 있다는 것을 간과했습니다.

예를 들어 1,1,1,1,1,1,1,1,1 같은 ... 

D까지 빨리 풀고싶네요. 화이팅 !

import sys
input = sys.stdin.readline

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

b = max(A)
result = [0] * (b+1)
dp = [0] * (b+1)
for i in range (1,b+1):
    for j in range (i,b+1,i):
        result[j] += i
    dp[i] = dp[i-1] + result[i]
for i in range (0,N):
    print(dp[A[i]])

#10164 격자상의 경로
import sys
import math
input = sys.stdin.readline
A,B,K = map(int,input().split())

if K == 0:
    print(math.comb(A+B-2,B-1))
else:
    x = (K-1) // B
    y = (K-1) % B 
    a = math.comb(x+y,y)
    b = math.comb(A+B-x-y-2,B-y-1)
    print(a*b)

#3130 붙인드롬
import sys
from itertools import product
input = sys.stdin.readline
N , M = map(int,input().split())

#2m 짝수자리의 palin
def palin_even(m):
    palin_list = []
    for palin in product(range(0,10),repeat = m):
        palin = list(palin)
        mirror = palin[::-1]
        palin = palin + mirror
        palin_list.append(palin)
    return palin_list

#2m-1 홀수자리의 palin 
def palin_odd(m):
    palin_list = []
    for palin in product(range(0,10),repeat = m):
        palin = list(palin)
        mirror = palin[::-1]
        mirror.remove(mirror[0])
        palin = palin + mirror
        palin_list.append(palin)
    return palin_list
 
if N % 4 == 0:
    A = palin_even(N//4)
    #앞자리가 0이 아닌 팰린드롬
    palin_1 = [0] * M
    #10^(N//2)로 나눈 나머지를 보존#
    palin_11 = [0] * M
    #앞자리가 0일수도있는 팰린드롬
    palin_2 = [0] * M
    for a in A:
        if a[0] != 0:
            b = "".join(str(s) for s in a)
            b = int(b) % M
            palin_1[b] += 1
            c = ((int(b) % M) * ((10 ** (N//2)) % M)) % M
            palin_11[c] += 1
        else:
            b = "".join(str(s) for s in a)
            b = int(b) % M
            palin_2[b] += 1
    cnt = 0
    for i in range (1,M):
        cnt += palin_11[i] * (palin_1[M-i] + palin_2[M-i])
    cnt += palin_11[0] * (palin_1[0] + palin_2[0])
    print(cnt)
else:
    A = palin_odd(int(N//4)+1)
    #앞자리가 0이 아닌 팰린드롬
    palin_1 = [0] * M
    #10^(N//2)로 나눈 나머지를 보존#
    palin_11 = [0] * M
    #앞자리가 0일수도있는 팰린드롬
    palin_2 = [0] * M
    for a in A:
        if a[0] != 0:
            b = "".join(str(s) for s in a)
            b = int(b) % M
            palin_1[b] += 1
            c = ((int(b) % M) * ((10 ** (N//2)) % M)) % M
            palin_11[c] += 1
        else:
            b = "".join(str(s) for s in a)
            b = int(b) % M
            palin_2[b] += 1
    cnt = 0
    for i in range (1,M):
        cnt += palin_11[i] * (palin_1[M-i] + palin_2[M-i])
    cnt += palin_11[0] * (palin_1[0] + palin_2[0])
    print(cnt)

몇번이나 시간초과를 당했어서 ...

결국 나머지를 list의 index에 대응시켜서 하나씩 올려주는 것으로 생각.

#3671 산업스파이의 편지
import sys
import math
from itertools import permutations
from itertools import combinations

N = int(input())
A = []

def f(n):
    if n == 0:
        return False
    elif n == 1:
        return False
    else:
        for i in range (2,int(math.sqrt(n))+1):
            if n % i == 0:
                return False
            else:
                continue
        return True

for i in range (0,N):
    a = input()
    A.append(a)

for i in range (0,N):
    prime = []
    for j in range (1,len(A[i])+1):
        num_list = list(A[i])
        for num in permutations(num_list,j):
            s = "".join(t for t in num)
            s = int(s)
            if f(s) == True:
                prime.append(s)
            else:
                continue
    prime = list(set(prime))
    m = len(prime)
    print(m)

Permutations을 잘 쓰면 되는 상황이고,
Permutations을 통해 찾아낸 숫자에 대해 소수판정을 해주는 방침으로 풀 수 있습니다.

파이썬 기준 2506ms가 나온 것으로 보아 정말 아슬아슬하게 푼듯한 느낌이네요.

import sys
import math

input =  sys.stdin.readline
A,B = map(int,input().split())

x = math.gcd(A,B) 
y = math.lcm(A,B)
z = y // x

result = []
divisor = []
for i in range (1,int(math.sqrt(z))+1):
    if z % i == 0:
        if math.gcd(i,z // i) == 1:
            b = [x*i,x*(z // i)]
            divisor.append(b)
            y = i + (z // i)
            result.append(y)
        else:
            continue
    else:
        continue

z = min(result)
c = result.index(z)
d = " ".join(str(s) for s in divisor[c])
print(d)

실행시간은 40ms

아이디어로는 "최소공배수를 최대공약수로 나눈 후, 몫을 서로소인 두 수의 곱으로 나타내는 것" 이겠다.

또 다른 예를 들어본다면 40과 90을 들어보자.

이 둘의 최대공약수는 10이며, 최소공배수는 360이다.
최소공배수 / 최대공약수 = 36 이며, 이를 서로소인 두 수의 곱으로 나타내는 방법은 (1,36), (4,9) 이렇게 두 쌍만 존재하는데

합을 최소로 하기 위해서는 4와9를 취하고, 최대공약수를 곱해주면 되겠다.

즉, 그대로인 40과 90가 되겠다.

#10422 괄호
import sys
import math
input = sys.stdin.readline
p = 1000000007
def catalan(n):
    return (math.factorial(2*n) // (math.factorial(n+1) * math.factorial(n))) % p

N = int(input())
result = []
for i in range (0,N):
    a = int(input())
    if a % 2 != 0:
        result.append(0)
    else:
        result.append(catalan(a//2))

for i in range (0,N):
    print(result[i])