★[python_파이썬_복습 또 복습]백준_13909번_창문 닫기_풀이

공부하는허딩크 : https://www.youtube.com/live/caDa0qD2i-c?feature=shared

일단 조건인 많은 것 같지만

결국 X의 배수일때 기존에 창문이 닫혀 있으면 +1을 하고 열려있으면 -1을 하는 구조이다.

 

<첫번째 시도 : 메모리 초과>

import sys

input = sys.stdin.readline

N = int(input())

graph = [0] * (N + 1)

for i in range(1, N + 1):

    for j in range(1, len(graph)):

        if j % i == 0:

            if graph[j]:

                graph[j] -= 1

            else:

                graph[j] += 1

print(sum(graph))

 

<두번째 시도 : 메모리 초과>

graph가 배열이 메모리를 더 필요로 하니까 리스트로 전환했는데 동일한 결과가 나왔다.

import sys

input = sys.stdin.readline

N = int(input())

graph = [0 for _ in range(N + 1)]

for i in range(1, N + 1):

    for j in range(1, len(graph)):

        if j % i == 0:

            if graph[j]:

                graph[j] -= 1

            else:

                graph[j] += 1

print(sum(graph))

 

<세번째 시도 : 메모리 초과>

이건 뭐.... 시도했다고 보기도 힘드네..

import sys

input = sys.stdin.readline

N = int(input())

graph = [0 for _ in range(N + 1)]

for i in range(1, N + 1):

    for j in range(1, len(graph)):

        if j % i == 0 and graph[j]:

            graph[j] -= 1

        elif j % i == 0 and not graph[j]:

            graph[j] += 1

print(sum(graph))

 

일단 규칙을 찾아 낸 것 같다. 사람이 1부터 있을때 모든 케이스를 그려서 공통요소를 찾는다. 조건이 아니다..... 젠장.

1 = 1                 

2 = 10

3 = 100

4 = 1001

5 = 10010

6 = 100100

7 = 1001001

8 = 10010010

9 = 100100100이렇게 흘러가는 걸 그림을 그려서 확인 할 수 있다.

즉 자리수가 있는데 3자리면 100, 6자리면 100100, 9자리면 100100100 이렇게 100이 반복된다.

이걸 이제 코드로 구현하는게 문제인데....3을 나눠서 나머지가 0이면 몫이 정답이 되고 나머지가 0이외면? 5 % 3 = 2라서?? 그냥 나머지만 2가 답??후.....  ==> 일단 이건 규칮이 아니다.

 

※위에 리뷰 작성하고 4일이 지났다. 이것저것 다른 것도 풀고 다시 리뷰 작성 중...

공부하는허딩크 : https://www.youtube.com/live/Io7CilXhjrk?feature=shared

<네번째 시도 : 메모리 초과>

기존 graph 리스트의 기본을 1로 채운 후 1의 배수일때 하던 동작을 필요 없게 만들었다.

그래서 range에서 2부터 시작할 수 있게 해서 연산의 개수를 줄였다. : 의미가 없는 감소인가?

N = int(input())

graph = [1 for _ in range(N + 1)]

for i in range(2, N + 1):

    for j in range(1, len(graph)):

        if j % i == 0 and graph[j]:

            graph[j] -= 1

        elif j % i == 0 and not graph[j]:

            graph[j] += 1

print(sum(graph) - 1)

 

<다섯번째 시도 : 메모리 초과>

2번째 for문의 범위를 줄이는 방법이다. 어차피 2부터는 2의 배수, 3부터는 3의 배수 4부터는 4의 배수 이렇게 떨어지기 때문에 쓸 수 있는 방법이었다. 

N = int(input())

graph = [0] * (N + 1)

for i in range(1, N + 1): # 1, 2, 3, 4

    for j in range(i, N + 1, i): # 1, 2, 3

        if j % i == 0:

            if graph[j]:

                graph[j] -= 1

            else:

                graph[j] += 1

print(sum(graph))

 

<여섯번째 시도 : 시간 초과>

이건 별도로 규칙을 찾고 난 이후에 생각할 수 있었다.

각 넘버의 변경되는 횟수를 기준으로 2번, 4번 이렇게 짝수로 변경되면 결국 최종 값은 0이기 때문에 생각할 수 있었다.

즉, 각 넘버의 변경되는 횟수를 num에 저장해서 홀수 일 경우 answer에 +1을 하는 방식이다.

N = int(input())

answer = 0

for i in range(1, N + 1):

    num = 0

    for j in range(1, i + 1):

        if i % j == 0:

            num += 1

    if num % 2 != 0:

        answer += 1

print(answer)

<규칙성 찾기>

<일곱번째 시도 : 시간초과>

여섯번째랑 비슷한 방식인데 기준을 소수로 정했다.규직을 보면 소수일때는 최종 자리가 0이 되는 것을 볼 수 있다.

즉 소수일때는 continue로 넘어가고 소수가 아닌 숫자들만 여섯번째와 동일하게 확인하는 방식으로 코딩을 만들었다.

 

#약수의 개수를 구해서 반복 : 시간초과

def Prime(n):

    if n <= 1:

        return 0

    for i in range(2, int(n ** 0.5) + 1):

        if n % i == 0:

            return 0

    return 1

N = int(input())

answer = 0

for i in range(1, N + 1):

    if Prime(i):

        continue

    else:

        num = 0

        for j in range(2, i):

            if i % j == 0:

                num += 1

        if i == 1:

            num += 1

        if num % 2 != 0:

            answer += 1

print(answer)

 

<여덟번째 시도 : 시간 초과>

모든 방법이 안되니 dict를 활용해서 넘버를 key값으로 해서 넘버가 변화하는 횟수를 Value값으로 저장 한 후

모든 Value값을 더해주는 방법을 찾았다. => 뭐라도 해봐야지....

#dict활용

dict = {}

N = int(input())

for i in range(1, N + 1):

    num = 0

    for j in range(1, i + 1):

        if i % j == 0:

            num += 1

    if num % 2 != 0:

        dict[i] = 1

print(sum(dict.values()))

 

<아홉번째 시도 : 위에 모든 방법을 버리고 규칙 찾기 : 맞았습니다. 드디어!!!!!!!>

규칙이 100100100이 아니라

100100001000000 이렇게 00이 2개씩 증가하는 규칙을 추정했다. ==> 아래의 표로 규칙을 일단 검증했다.

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

 

즉 123 일때는 답이 1이고 => 숫자 3개

    45678 일때는 답이 2이고 => 숫자 5개

    9101112131415 일때는 답이 3이고 => 숫자 7개... 이렇게 뛰네? 규칙성이 보이긴 하는데....

import sys

input = sys.stdin.readline

N = int(input())

answer = 0

while N > 0:

    if N <= 3:

        answer += 1

        break

    else:

        answer += 1

        N -= (2 * answer) + 1

print(answer)

 

규칙을 찾고 코드를 작성했다.

3 : 2 * answer + 1

5 : 2 * answer + 1

7 : 2 * answer + 1

9 : 2 * answer + 1

=> answer가 1, 2, 3, 4, 5 이렇게 나올 수 있다.

숫자 3개, 5개, 7개 이렇게 증가할때마다 +1씩 해야하니까 주어진 수에서 각 숫자들을 마이너스를 해준다.

그 전에 answer에 + 1씩해주면 최종 답을 구 할 수 있다.

 

이거 생각하기까지 오래 걸렸다. 일단 규칙을 찾는데 시간을 많이 허비 했고, 규칙을 찾은 후에도 저렇게 코드를 작성하는 것도 쉽지 않았다.

 

<다른 사람풀이 참고>

대박. 이렇게 풀 수도 있었구나...

1. inr(math.sprt(N)) ==> 와.... 이 규칙도 외워야지....

1, 2, 3의 제곱근은 1

4, 5, 6, 7, 8의 제곱근은 2

9, 10, 11, 12, 13, 14, 15의 제곱근은 3

16, 17, 18, 19, 20, 21, 22, 23, 24의 제곱근은 4....

이 방식이구나 ==> OK. 접수했어!!!!!!

import sys

input = sys.stdin.readline

N = int(input())

print(int(N**0.5))