[BOJ/백준] 2437번 저울

문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 입력 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는..

• format_list_bulleted Algorithm
• · 2021. 2. 9.
• textsms

[BOJ/백준] 1439번 뒤집기

문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력 첫째 줄에 문자열 ..

• format_list_bulleted Algorithm
• · 2021. 2. 8.
• textsms

[BOJ/백준] 1647번 도시 분할 계획

문제 동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안..

• format_list_bulleted Algorithm
• · 2021. 2. 8.
• textsms

[BOJ/백준] 1929번 소수 구하기

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 풀이 a,b = map(int,input().split()) #두개의 값을 띄어쓰기로 구분지어서 입력 def prime(num): #소수 찾는 함수 if num == 1: #1이면 False return False elif num ==2: #2부터는 True return True for i in range(2,int(num**0.5)+1): #에라토스테네스의 체를 안다면 제곱근을 이용해서 푸는것이 시간 단축에 좋음 if..

• format_list_bulleted Algorithm
• · 2021. 2. 5.
• textsms

[BOJ/백준] 11653번 소인수분해

문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 풀이 a = int(input()) # 입력 값 선언 i = 2 # 1은 무조건 나누어 지기 때문에 2부터 순회 while a != 1: # 입력 값이 나누어 질 때 마다 1에 가까워 지기 때문에 1이 된다면 종료 if a % i == 0: # 입력 값이 나누어진다면 나누어진 값으로 a를 초기화 a //= i print(i) # i값이 나누어진 소인수 이기 때문에 출력 else: i += 1 # 나누어 지지 않는다면 i를 1씩 증가 코드 풀이 주석으로 대체

• format_list_bulleted Algorithm
• · 2021. 2. 5.
• textsms

[BOJ/백준] 1978번 소수 찾기

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 풀이 n = int(input()) #입력받을 개수 arr = list(map(int,input().split()))#소수인지 판별할 배열 입력 def prime(num): #소수 판별 함수 if num == 1: return False elif num == 2: return True for i in range(2,num): if num % i == 0: return False return True cnt = 0 for i in arr: if p..

• format_list_bulleted Algorithm
• · 2021. 2. 5.
• textsms

<