숫자 카드 게임

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

입력
첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1<=N,M<=100)
둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

출력
첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

해결 아이디어

각 행마다 가장 작은 수를 찾은 뒤 그 수 중에서 가장 큰 수 찾기!

n,m=map(int, input().split())
result=0
for i in range(n):
  data=list(map(int, input().split()))
  min_value=min(data)
  result=max(result,min_value) #result값 갱신하면서 행별로 최댓값 비교 가능
result

1이 될 때까지

어떠한 수 N이 1이 될 때까지 반복해서 수행, 단 2번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다
2. N을 K로 나눈다.

과정 수행을 최소 횟수로 하는 프로그램 작성하기

해결 아이디어
주어진 N에 대해 최대한 많이 나누기를 하면 작업 수를 훨씬 많이 줄일 수 있다.

n,k=map(int, input().split())
result=0
while True:
  result+=n%k #1을 빼는 연산 횟수
  n=target
  # n이 k보다 작을 때 더이상 나눌 수 없으니 반복문 탈출 
  if n<k:
    break
  # k로 나누기 (// 연산기호: 나머지 소숫점 이하 버리는 나누기)
  n//=k
  result+=1 # 나눠지는 연산 개수 하나씩 추가
  print(result)
# 마지막 남은 수에 대해 1씩 빼서 횟수 더하기
result+=(n-1)
print(result)

모험가 길드

공포도 x인 모험가는 반드시 x 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다. 최대 몇 개의 모험가 그룹을 만들 수 있을까. 여행을 떠날 수 있는 그룹 수의 최댓값을 구하라.

해결 아이디어

• 현재 그룹에 포함된 모험가 수가 현재 확인하고 있는 공포도보다 크거나 같다면 이를 그룹으로 설정하면 된다.
  
• 공포도가 오름차순으로 정렬되어 있으면 항상 최소의 모험가 수만 포함하여 그룹을 결성할 수 있다. 모든 모함가를 특정한 그룹에 넣을 필요가 없기 때문!

n=int(input())
data=list(map(int, input().split()))
data.sort()
result=0 # 총 그룹 수
count=0 # 현재 그룹에 포함된 모함가 수
for i in data: # 공포도 낮은 것부터하나씩 확인
  count+=1 # 현재 그룹에 해당 모함가 포함시키기
  if count>=i: # 해당그룹에 포함된 모험가 수가 현재 공포도 이상이라면, 그룹 결성
    result+=1 # 총그룹의 수도 증가시키기
    count=0 # 현재 그룹에 포함된 모험가 수 초기화
  print(result, count)
print(result)

곱하기 혹은 더하기 문제

0~9로 이루어진 문자열에서 왼쪽부터 하나씩 모드 숫자가 x 혹은 + 연산자를 넣어 만들 수 있는 가장 큰 수 구하는 프로그램을 만들기

해결 아이디어
두 수 중 0 또는 1인 경우, 곱하기보다 더하는게 더 효율적이다.

data=input()
# 첫번째 문자를 숫자로 변경해서 대입
result=int(data[0])
for i in range(1,len(data)):
  # 두 수 중 하나라도 1이하인 경우 더하기 수행
  num=int(data[i])
  if num<=1 or result<=1:
    result+=num
  else:
    result*=num

print(result)

문자열 뒤집기

0과 1로 되어있는 숫자를 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것

예를 들어 s=0001100 일 때, 4,5번째 1을 0으로 뒤집으면 한번 만에 같은 숫자로 만들 수 있다.

최소 횟수는?

data=input()
cnt0=0 #전부 0으로 바꾸는 횟수 = 1 뒤집는 횟수
cnt1=0 #전부 1로 바꾸는 횟수
if data[0]=='1':
  cnt0+=1
else:
  cnt1+=1
for i in range(len(data)-1):
  if data[i]!=data[i+1]:
    if data[i+1]=='1':
      cnt0+=1
    else:
      cnt1+=1
print(min(cnt0,cnt1))

만들 수 없는 금액

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하라.

예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정한다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.

또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정한다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다.

입력
첫 째줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. (1≤N≤1,000)
둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수이다.

출력
첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.

해결 아이디어
화폐단위 기준으로 정렬한 뒤, 작은 동전부터 확인하면서 target을 업데이트하는 방법

k=1,2,3,8 일 때 순서

1. target=1로 설정
2. 1존재하니, 1+1=2로 타겟 변경
3. 2존재하니, 2+2=4로 타겟 변경
4. 3존재하니(* 타겟보다 작아야함) 4+3=7로 타겟 변경
5. 타겟 7보다 8이 더 크므로 멈추고, 만들 수 없는 돈 액수는 7이다.

• 내가 푼 방법
  복잡하고 어렵,,, 가능한 순열 다 뽑아서 정렬하고 다음 숫자와 차이가 1이상 나는 것 따로 저장한다.
  모든 경우의 수를 다 계산해서 시간이 훨씬 오래 걸릴 것이다……!

n=int(input())
k=list(map(int, input().split()))
b=[]
for i in range(1,n+1):
  per=list(permutations(k,i))
  for j in per:
    b.append(sum(j))
    b=list(set(b))
target=0
for i in range(len(b)):
  if b[i+1]!=b[i]+1:
    target=b[i]+1
    break
print(target)

• 책에서 푼 방법

n=int(input())
k=list(map(int, input().split()))
k.sort()
target=1
for i in k:
	if target<i:
		break
	target +=i
print(target)