JH 개발 블로그

n = int(input())
coin = [list(input()) for _ in range(n)]
ans = n * n + 1

for bit in range(1 << n):
    tmp = [coin[i][:] for i in range(n)]
    for i in range(n):
        if bit & (1 << i):
            for j in range(n):
                if tmp[i][j] == 'H':
                    tmp[i][j] = 'T'
                else:
                    tmp[i][j] = 'H'

    tot = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if tmp[j][i] == 'T':
                cnt += 1
        tot += min(cnt, n-cnt)
    ans = min(ans, tot)

print(ans)

각 동전마다 뒤집는다/ 안뒤집는다 2가지 경우의 수가 있습니다.

만약 n개의 동전이 있다면 총 경우의 수는 2^n개가 됩니다.

tmp 각 열에서 T의 개수가 H보다 많다면, 열을 뒤집었다 칩니다.(n-cnt)

import bisect
import sys

input = sys.stdin.readline
x = int(input())
arr = list(map(int, input().split()))

temp = [arr[0]]

for i in range(x):
    if arr[i] > temp[-1]:
        temp.append(arr[i])
    else:
        idx = bisect.bisect_left(temp, arr[i])
        temp[idx] = arr[i]
        
print(len(temp))

이분탐색 bisect 모듈의 bisect_left 함수를 통해 수열을 계속 수정하면서 답을 구합니다.

n,m = map(int,input().split())

def solution():
    if n == 1:
        return 1
    elif n == 2:
        return min(4,1+(m-1)//2)
    else:
        if m <= 6:
            return min(4,m)
        else:
            return m-2

print(solution())

문제 설명이 불친절한거 같습니다.

이동횟수가 4 이상이면, 이동방법 1~4를 모두 최소 한번씩은 사용한 상태여야 합니다.

n이 1,2,3 일때로 경우의 수를 나눠서 풀면 됩니다.

def solution():
    n,k = map(int,input().split())

    a = 0
    b = n
    while a*b < k and b > 0:
        a += 1
        b -= 1

    if k == 0:
        return 'B'*n
    elif b == 0:
        return -1

    remain = k - (a-1)*b

    return 'A'*(a-1) + 'B'*(b-remain) + 'A' + 'B'*remain

print(solution())

import sys

input = sys.stdin.readline
R,C = map(int,input().split())

if R%2 == 1:
    ans = ''
    for r in range(R):
        if r%2 == 0:
            ans += 'R'*(C-1)
        elif r%2 == 1:
            ans += 'D'+'L'*(C-1)+'D'
    print(ans)
elif C%2 == 1:
    ans = ''
    for c in range(C):
        if c%2 == 0:
            ans += 'D'*(R-1)
        elif c%2 == 1:
            ans += 'R'+'U'*(R-1)+'R'
    print(ans)
else:
    min_idx,min_val = [0,0],1000
    for r in range(R):
        if r%2 == 0:
            temp = list(map(int,input().split()))
            for c in range(1,C,2):
                if temp[c] < min_val:
                    min_val,min_idx = temp[c],[r,c]
        elif r%2 == 1:
            temp = list(map(int,input().split()))
            for c in range(0,C,2):
                if temp[c] < min_val:
                    min_val,min_idx = temp[c],[r,c]

    ans = ('R'*(C-1)+'D'+'L'*(C-1)+'D')*(min_idx[0]//2)
    r,c = 2*(min_idx[0]//2),0
    nr,nc = min_idx[0],min_idx[1]
    r_bound = r+1
    while r != r_bound or c != C-1:
        if r < r_bound and [r_bound,c] != min_idx:
            r += 1
            ans += 'D'
        elif r == r_bound and [r_bound-1,c] != min_idx:
            r -= 1
            ans += 'U'
        if c != C-1:
            c += 1
            ans += 'R'

    ans += ('D'+'L'*(C-1)+'D'+'R'*(C-1))*((R-1-min_idx[0])//2)

    print(ans)

1. R이 홀수일때

2. C가 홀수일때

3. R,C 둘다 짝수일때

경우의 수를 3개로 나눠서 조건에 맞게 구현하면 됩니다.

R,C 둘다 짝수 일때가 중요한데,

모든 좌표를 다 방문할 순 없습니다. 최소 한개의 좌표는 방문하지 못합니다.
그렇다면 최대기쁨을 구하는방법은 최소기쁨인 좌표 한군데만 방문하지 않는것입니다.

그런데, 여기서 알아야 할게 있습니다. 최소기쁨인 칸의 좌표를 [r,c] 라고 했을 때
만약 r+c가 짝수라면, 좌표 [r,c]를 방문하지 않을 뿐 아니라 추가적으로 방문하지 못하는 좌표(홀수)가 생깁니다.
하지만 r+c가 홀수라면, 오직 좌표[r,c] 하나만 방문하지 않습니다.

따라서 r+c가 짝수라서 좌표 [r,c]도 방문하지 않고, 추가적으로 홀수 좌표도 방문하지 않는다면
차라리 홀수 좌표 중에서 최소기쁨인 칸을 찾아내서, 그 칸만 방문하지 않으면 됩니다.

최소값 근처까지 이동한 후, while 문으로 최소값 근처에서의 이동경로를 구하고 그 다음에 목적지까지 이동하는 식으로 구현하면 됩니다.

https://www.acmicpc.net/problem/11664

ax,ay,az,bx,by,bz,cx,cy,cz = map(int,input().split())

ans = float('inf')

while True:
    mx,my,mz = (ax+bx)/2,(ay+by)/2,(az+bz)/2
    l = ((ax-cx)**2+(ay-cy)**2+(az-cz)**2)**0.5
    h = ((mx-cx)**2+(my-cy)**2+(mz-cz)**2)**0.5
    r = ((bx-cx)**2+(by-cy)**2+(bz-cz)**2)**0.5

    if abs(ans-h) <= 1e-6:
        print('%0.10f'%ans)
        exit()
    if h < ans:
        ans = h
    if l > r:
        ax,ay,az = mx,my,mz
    else:
        bx,by,bz = mx,my,mz

점 a를 선분의 왼쪽에 있는 점, 점 b를 선분의 오른쪽에 있는 점이라 생각합니다.

점 a와 점 b의 중간점 m을 구합니다.

l = 점 a와 점 c의 거리

r = 점 b와 점 c의 거리

h = 점 m과 점 c의 거리

를 계산해줍니다.

만약 h가 현재 존재하는 최소값 ans보다 작다면, ans를 h로 갱신해줍니다.

만약 l이 r보다 크다면, c가 a보다 b에 더 가깝게 있다는 뜻이므로 점 a를 점 m으로 바꿔줍니다.

(이분탐색을 진행해야 하므로 더 가까운 쪽으로 범위를 좁혀줘야 하기 때문입니다.)

반대로 r이 l보다 크다면 c가 b보다 a에 더 가깝게 있다는 뜻이므로 점 b를 점 m으로 바꿔줍니다.

위 작업을 반복합니다. 만약 ans와 h의 차가 오차범위 안에 들어왔다면, 정답을 출력하고 종료합니다.

m을 구할 아이디어를 떠올리는게 포인트라고 생각합니다.