투투

문제 1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치에서 1은 켜져있고 0은 꺼져 있음을 나타낸다. 학생들에게 1이상이고 스위치 개수 이하인 자연수를 하나씩 나누어준다. 학생들은 자신의 성별과 받은 수에 따라 스위치를 조작한다. 남학생은 자신이 받은 수의 배수에 있는 스위치의 상태를 바꾼다. 여학생은 자신이 받은 수를 중심으로 좌우 대칭인 곳까지의 스위치 상태를 바꾼다. 학생들이 스위치를 조작했을 때 스위치들의 마지막 상태를 출력하라. 입력 첫째 줄에 100이하인 스위치의 개수가 주어진다. 둘째 줄에는 스위치의 상태가 주어진다. 셋째 줄에는 학생수가 100이하로 주어진다. 이후부터 학생의 성별과 학생이 받은수가 주어진다. 남학생은 1, 여학생은 2로 표시한다. 출력 마지막 스위치의 상태를 출력..

문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 조합의 결과를 출력한다. 접근 먼저 조합은 N개의 원소 중에서 M개를 순서에 상관없이 선택하는 경우의 수다. 이를 구하기위한 공식이 존재하며 다음과 같다. 따라서 다음의 식대로 구현을 하였다. 구현 팩토리얼을 math 모듈의 factorial()을 사용하였다. import math N, M = map(int, input().split()) answer = math.factorial(N) // (math.factorial(N-M) * math.factorial(M)) print(answer)

문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 선택한 M개의 수를 나열한다. 접근 M개의 수를 선택하기위해 백트래킹을 사용하였고 선택할 수를 찾는 인덱스를 0부터 시작하여 찾도록 하였다. 구현 아직 선택하지 않은 수 중에서 숫자를 선택할 때 처음부터 탐색을 하도록 하였다. 왜냐하면 (1, 7)과 (7, 1)은 다른 조합이기 때문에 이 두 개의 조합도 출력하도록 하였다. def ..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 N과 M이 주어진다. 1 ≤ M ≤ N ≤ 8 출력 한 줄에 선택한 M개의 수를 출력한다. 중복으로 출력할 수 없고 오름차순으로 출력한다. 접근 백트래킹으로 1차원 리스트에 저장된 수열을 M개 선택하도록 하였다. 구현 다음은 N개의 수열 중에서 M개를 선택하는 함수이다. 선택된 수는 picked라는 리스트에 저장하게되며 리스트의 길이가 M이 되었을 때 리스트 안에 있는 수를 출력한다. 만약 아직 M개를 선택하지 못했다면 선택하지 않은 수들을 골라 리스트에 넣어주고 재귀호출을 한다. de..

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 접근 변의 길이가 증가하는 규칙을 찾아보면 현재 i번째 길이를 구한다고 했을 때 (i-2) + (i-3)을 통해 구한다. 따라서 위의 점화식을 토대로 구현하도록 한다. 구현 초기 세 개의 길이를 1로 초기화하고 이후의 길이는 i = (i-2) + (i-3)이라는 점화식을 통해 구하도록 한다. test_case = int(input()) for tc in range(test_case): N = int(input()) ..

문제 프린터는 다음과 같은 조건에 따라 인쇄된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 프린터의 문서 수가 주어졌을 때 어떤 문서가 몇 번째로 출력되는지 구하라 입력 첫째 줄에 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에 문서의 수와 확인하고자 하는 문서의 위치를 입력하고 이어서 문서의 중요도를 입력한다. 출력 확인하고자 하는 문서가 몇 번째로 인쇄되는지 출력한다. 접근 문서들의 위치에 따른 중요도를 큐에 담는다. 그리고 중요도가 큰 것과 같으면 pop을 하고 그렇지 않다면 front에 있는 문서를 ..

문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 접근 유클리드 호제법을 통해 최대공약수와 최소공배수를 구해보았다. 먼저 최대공약수를 구하기 위해서 두 수 A와 B가 A>B일 때 B가 0이 될 때까지 A%B를 A에 대입한다. 그리고 A와 B의 값을 교환한다. B가 0이 되는 순간의 A값이 최대공약수가 된다. 또한 최소공배수는 A*B를 최대공약수로 나눠주면 된다. 그 이유는 A와 B의 최대공약수는 두 수 사이에 겹치는 공약수 중 ..

www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 접근 ord()를 통해 문자를 숫자로 변경 후에 각각 96을 빼주어 a가 1이 되도록 하였다. 구현 N = int(input()) word = input() answer = 0 for idx in range(N): answer += (ord(word[idx])-96) * (31**idx) print(answer%1234567891)

www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 접근 N! / K!(N-K)! 를 그대로 구현을 하였다. 하지만 math에서 factorial이 있다는 것을 알게되었다. 팩토리얼 안쓰고 구현 N, K = map(int, input().split()) D = 1 t = N-K while N > 0: D *= N N -= 1 M = 1 while K > 0: M *= K K -= 1 while t > 0: M *= t t -= 1 print(D//M) 팩토리얼 연산 from math import factorial N, K = map(in..

문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다. 접근 처음에는 while문으로 A만큼 빼고 B를 더하도록 하였지만 시간초과가 발생하였다. 이후 규칙을 찾으려고 하였다. 하루에 A-B만큼 올라가게 되고 V로 나누려고 했지만 밤에 자는 동안 떨어..