_

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 접근법 #규칙 발견이었는데 n에 대한 개수들을 잘못 찾아 규칙을 발견하지 못하여 이건 결국 찾아봄.. 규칙 : arr[i]=arr[i-1]+arr[i-2]*2 코드 n=int(input()) arr=[0]*(n+1) arr[1]=1 if n!=1: arr[2]=3 for i in range(3,n+1): arr[i]=arr[i-1]+arr[i-2]*2 print(arr[n]%10007)

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 접근법 2부터 순서대로 나열을 해보니 피보나치 수열임을 확인 피보나치 수열은 arr[i]=arr[i-1]+arr[i-2]의 규칙을 갖고 있음. 피보나치 수열을 적용해 마지막 값까지 구하고, arr[n]을 10007로 나눈 나머지를 출력 코드 n=int(input()) arr=[0]*(n+1) arr[1]=1 if n!=1: arr[2]=2 for i in range(3,n+1): arr[i]=arr[i-1]+ar..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 접근법 처음엔 x가 2로 나눠질 때, 3으로 나눠질 때, -1로 빼기를 if문으로 했었는데 입력받은 수 10일 때 안됨을 확인했음. 반례가 바로 다행히 나와서 다른 접근법을 구상해야했고, 동적 알고리즘은 처음 접하기에 사용법 검색 동적 접근법, 즉 다이나믹 프로그래밍은 memoization을 주로 활용 같은 것을 계속 반복하면 시간을 잡아먹으니 한번 찾은 건 저장해놓음으로써 반복의 횟수를 줄여주는 방식 다이나믹 프로그래밍은 상향식, 하향식이 존재 이 문제는 입력받은 수까지의 여정을 그리는 게 나아 상향식 ..

https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 접근법 소인수분해된 값들은 소수들로 이루어져있으니 소수들을 먼저 구해야한다 생각함. 때문에 입력받은 수까지의 소수를 구해서 소수 2부터 시작해서 입력받은 수가 1이 될 때까지 나눠지는 소수들을 순서대로 출력 (2로 나눴을 때 나머지가 0이 나오면 계속 2로 나누다 0이 아니면 다음 소수인 3으로 넘어가기) 입력받은 수가 1이면 바로 종료 코드 n=int(input()) if n==1: exit() prime=[True]*(n+1) prime[1]=False for i in range(2,int(n**0.5)+1..

https://www.acmicpc.net/problem/11576 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net 문제 접근법 1. 입력받은 arr을 각 자릿수에 맞춰 계산 후 10진법으로 변환 2. 출력할 때 자릿수 사이에 띄어쓰기를 넣어줘야 하므로 변환 직전마다 공백 넣기 3. 변환된 10진법의 수를 B진법으로 변환 코드 A,B=map(int, input().split()) m=int(input()) arr=list(map(int,input().split())) a=0 for i in r..

https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문제 접근법 1. 입력받은 N의 끝부분부터 역으로 출력 2. 해당 부분이 숫자인지 문자인지 확인 3. 숫자는 int형으로 변환, 문자는 아스키코드 변환 후 A=10이 나오게 숫자 조정 (A의 아스키 코드는 65, 문제에서 A는 10을 필요로 하므로 55를 빼기) 4. 진법변환 공식을 통해 순차적으로 제곱하며 곱해주고 ans에 더하기 코드 N,B=input().split() B=int(B) ans=0..

https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문제 접근법 #문제를 이해하지 못해 검색해봄. 다시 풀어볼 것! 1. 0~35까지에 알맞는 숫자 또는 문자를 nums에 배치 2. 10진법 수인 N을 진법B로 나눠서 나온 나머지를 nums에 매칭 후, 앞에서부터 저장 코드 nums='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' N,B=map(int,input().split()) ans='' while N: ans=nu..

https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 문제 접근법 1. 입력받은 수들 중 큰 수 구하기 2. 큰 수만큼 소수 구하기 3. 입력받은 수의 절반까지 안에서 소수들의 합 찾기 ##시간초과가 나서 검색을 해봤는데 다들 내가 푼 풀이랑 똑같이 풀었다. 다른 게 있다면, 수들을 입력받을 때 append와 리스트에서 [-1]을 사용했다는 것이다. 때문에 혹시나해서 append 대신 미리 크기를 지정해서 대입을, [-1]대신 대입을 사용했더니 시간초..

https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net 문제 접근법 # 도저히 접근법을 모르겠어서 검색해봄. 나중에 다시 풀어보기 -2로 N을 계속 나눠줌. 나머지가 1과 0이 나와야 함. 따라서 0이 나왔을 때는 그대로 진행하여 몫과 나머지 그대로 사용 -1이 나오면 몫에 +1을 해주고 나머지는 1로 처리 나온 나머지들을 앞에서부터 쌓아 ans 만듦. ..

https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 문제 21.03.13 접근법 8진수를 10진수로 변환 후, format함수를 이용해 2진수로 변환 21.03.13 코드 n=int(input(),8) print(format(n,'b')) 21.08.26 접근법 8진수를 10진수로 변환 후, format함수를 이용해 2진수로 변환 21.08.26 코드 print(format(int(input(),8),'b'))