짹짹쌤의 놀이터

https://www.acmicpc.net/problem/2960

안녕하세요~

백준 2960번 에라토스테네스의 체 >>>>>쉬운<<<<< 문제 풀이를 가지고 왔습니다!

먼저 예제 입력 1과 예제 출력 1를 가지고 문제를 이해해보도록 하겠습니다.

저는 그래서 이 문제를 보았을 때 2부터 주어진 N 값까지 있는 리스트를 만들어서

2의 배수를 없애고, 3의 배수 없애고... 그러면서 카운트에 1씩 더하면서

카운트 값과 K 값이 같아질 때 해당 수를 출력하면 되겠구나!

하는 생각을 하면서 문제에 접근을 했는데 잘 안되더라고요...

검색창에 해설을 검색해봐도 저에게는 너무 어려운 풀이들만 나와서 이해가 어려웠습니다ㅠㅠ

그래서 역발상을 하기로 했습니다. 

(여기에 도달하기까지 몇 시간 걸렸다는건 안비밀...ㅠ,ㅠ)

리스트에서 제거하는 방식이 아니라,
직접 지워지는 수를 리스트에 채워나가면 어떨까?

이런 방식으로 푼 코드 입니다!  물론 정답이었습니다!

자세히 설명해보자면 이런 느낌입니다.

n, k = map(int,input().split()) #n과 k값을 받기
a = int(n/2) + 1 #두번째 for 문에서 최대 몇으로 할지 결정하기 위한 값
l = [] #리스트 생성

for p in range(2,n+1): #p의 값 조절! 가장 작은 숫자 2부터 시작
  for i in range(1,a): #배수를 구하기 위한 부분
    if p*i <= n:     # n보다는 작을 때
      l.append(p*i)  # 리스트에 값 추가

#중복 제거용  예) 2의 배수 6이 3의 배수 6과 중복되는 현상 발생
new_list=[]
for num in l:
  if num not in new_list:
    new_list.append(num)

print(new_list[k-1])

▶ 2번째 줄 코드

     어차피 p 값의 가장 작은 수는 2입니다. 2의 배수부터 지워나간다는 뜻입니다.

     그러므로 N값을 2로 나눠서 몇 번 반복해야하는지를 계산하기 위한 것입니다.

     +1 이 있는 이유는 N값이 홀수인 경우가 있기 때문입니다.

▶ 중복 제거?

     중간의 중복 제거용이 필요한 이유는 위 표에서 표시한 숫자처럼 4, 6, 8 등 배수가 겹치는 현상이 발생했기 때문입니다.

사실 검색창에 검색해보시면 이런 풀이가 아닌 Boolean 형을 활용해 문제를 푸시던데..

전 잘 모르겠더라고요...

그래서 수학적으로(?) 접근하여 문제를 해결했습니다!

정말 이 문제 풀고 나서 얼마나 기뻤는지...큽 8ㅅ8

다른 분들께도 도움이 되셨기를 바랍니다!

https://www.acmicpc.net/problem/2745

요즘 파이썬을 공부하면서 백준 문제를 천천히 풀어나가고 있습니다.

먼저 문제를 이해해보도록 하겠습니다.

보시는 것처럼 예제로 이해해보면

첫번째 Z : 35 X 36의 4제곱 = 58,786,560

두번째 Z : 35 X 36의 3제곱 = 1,632,960

세번째 Z : 35 X 36의 2제곱 = 45,360

네번째 Z : 35 X 36의 1제곱 = 1,260

마지막 Z : 35 X 36의 0제곱, 즉 1이 곱해져서 36 입니다.

이 모든 숫자를 더하면?

58,786,560 +  1,632,960 + 45,360 + 1,260 + 36 = 60,466,176

예제 출력에 나와있는 수가 출력이 되는 것을 알 수 있습니다.

규칙성이 보이시나요?

그래서 저는 N 값을 딕셔너리화 시켜서 문제를 해결했습니다!

이 문제를 보자마자 어떻게 풀까 고민하다가 코랩에서 이렇게 풀었습니다!

# 첫번째 문제 풀이 (백준 사이트에서는 런타임에러(KeyError) 발생)

N, B = input().split() 			# 두 값 받기
B = int(B)             			# 정수형 변환
n = len(N)			        # N의 길이를 변수 n에 저장
list_N=list(N)        		       # N을 리스트로 만듦

#각 알파벳을 대입할 딕셔너리 생성 (알파벳이 key, 숫자가 value)
dic = {'A':10,'B':11,'C':12,'D':13,'E':14,'F':15,'G':16,'H':17,'I':18,'J':19,'K':20,'L':21,'M':22,'N':23,'O':24, 'P':25,'Q':26,'R':27,"S":28,'T':29,'U':30,'V':31,'W':32,'X':33,'Y':34,'Z':35}

sum = 0 			   # 합계를 계산할 변수 sum 

for i in list_N:      		   # 리스트로 만든 N으로 반복
  sum += int(dic[i]) * (B**(n-1))  # sum에 각 알파벳의 key 값에 B진법 계산
  n -= 1            		   # n 값을 1씩 빼줌

print(sum) 			   # 합계 출력

코랩에서는 분명 맞았단 말이죠? 정답이었습니다!

당연하죠! 틀리지 않았으니까요?

그.런.데

틀렸다고 나오더라고요?

띠용 했어요... 뭐지? 코드 안틀렸는데?

그런데 찾아보니... 단 두 줄로 끝나는 거더라고요????

# 두번째 문제 풀이 (백준에서 정답 처리됨)

n, b = input().split()
print(int(n,int(b)))

어이가 없어서...

파이썬은 int 함수를 이용해서 n진법을 10진법으로 변환할 수 있다고 해요.

int(변환할 문자열, int(n진법)) 이렇게 쓰면 된다고 합니다.... n진법은 int형으로 써주기!

이럴 수가... 좀 약간 억울..?

저는 A 값에 10이 저장되어 있고 이런 것을 몰랐었습니다..

(사실 코드 짜면서 이게 맞나..? 하는 의문이 들긴 했습니다.. 딕셔너리 만들 때요...

이렇게 하나하나 알파벳을 입력해서 값을 넣어야하나 고민했습니다...)

좀 황당하더라고요..흐엉 (일일히 쓴 나는 뭔가...)

이렇게 배워가는 거겠죠ㅠ_ㅠ

이상으로 백준 2745번 2가지 문제 풀이 였습니다!