from sys import stdin
input = stdin.readline

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

chessTable = []
for i in range(n):
  s = input().rstrip()
  chessTable.append(list(s))
  # list(map(~~)) 이대로 입력 받으니까 문자열 자체가 한개의 요소라서 개별문자 접근이 안됨

def paint_chessTable(arr, y, x):
  
  s1 = "WBWBWBWB" # 번갈아가면서 확인해야함
  s2 = "BWBWBWBW"
  cnt = 0
  for i in range(y, y + 8):
    idx = 0
    for j in range(x, x + 8):
      if i % 2 == 0:
        if arr[i][j] != s1[idx]:
          cnt += 1
      else:
        if arr[i][j] != s2[idx]:
          cnt += 1
      idx += 1

  return min(cnt, 64-cnt) # 반대 경우의 수 : 최대 경우의 수(64) - 현재 경우의 수

answer = n * m # 최악의 경우에도 32는 넘지 않지만 대충 크게 넣음

for i in range(n):
  for j in range(m):
    # 인덱스가 넘지않는 범위 내의 8x8
    if i + 8 <= n and j + 8 <= m:
      answer = min(answer, paint_chessTable(chessTable, i, j))

print(answer)

구현하는데 시간이 너무 오래걸림

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int n, m;
	int answer = 0;

	deque<int> rq;
	deque<int> nums;

	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		int data;
		cin >> data;
		nums.push_back(data);
	}

	for (int i = 1; i <= n; ++i)
	{
		rq.push_back(i);
	}

	for (auto& num : nums)
	{
		int idx = find(rq.begin(), rq.end(), num) - rq.begin();
		while (num != rq.front())
		{
			// 왼쪽으로 밀기
			if (idx < (int)rq.size() - idx)
			{
				rq.push_back(rq.front());
				rq.pop_front();
			}
			else
			{
				rq.push_front(rq.back());
				rq.pop_back();
			}
			answer++;
		}
		rq.pop_front();
	}

	cout << answer;

	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int n, m, data, v_size;
	vector<int> v1, v2;

	cin >> n >> m;

	v_size = n > m ? n : m;

	while (n--)
	{
		cin >> data;
		v1.push_back(data);
	}	
	while (m--)
	{
		cin >> data;
		v2.push_back(data);
	}

	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());

	vector<int> v3(v_size);

	// find에서 begin을 빼주면 index를 구할수 있는걸 응용함
	// 두 집합 결과의 다음 iterator가 반환되기때문에 begin을 빼주면 원소의 개수가 된다
	auto ans1 = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()) - v3.begin();
	auto ans2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v3.begin()) - v3.begin();

	cout << ans1 + ans2 << '\n';

	return 0;
}

다른사람 풀이(46781878)는 이진 탐색으로 교집합 되는 원소의 개수(C)를 구한 뒤 N+M-(2*C)로 정답처리를 받았다.

from sys import stdin
from collections import Counter
input = stdin.readline

n = int(input())

arr = []
arr_sum = 0
for i in range(n):
  data = int(input())
  arr_sum += data
  arr.append(data)

arr.sort()
d = sorted(dict(Counter(arr)).items(), key=lambda x:(-x[1],x[0]))
# 더 심플하게 수정가능. d = Counter(arr).most_common(2)

print(round(arr_sum/n)) # 산술 평균
print(arr[n//2]) # 중앙값
if d[0][1] == d[1%n][1]: # 최빈값
  print(d[1%n][0])
else:
  print(d[0][0])
print(abs(arr[0] - arr[-1])) # 최대-최소 차이

Counter 처음써봤다. 다른사람 소스 보고 most_common의 존재를 알아서 다행임

from sys import stdin
input = stdin.readline

# 문자열로 받아서
n = input().rstrip()

arr = []
for i in range(len(n)):
  # 숫자로 쪼개 넣은뒤
  arr.append(int(n[i]))

# 내림차순 정렬
arr.sort(reverse=True)

for i in arr:
  print(i, end='')

#include <iostream>
#include <vector>
#include <algorithm>

#define horizon first
#define index second

using namespace std;

bool cmp_horizon(pair<int, int>& v1, pair<int, int>& v2)
{
	return v1.horizon < v2.horizon;
}

bool cmp_index(pair<int, int>& v1, pair<int, int>& v2)
{
	return v1.index < v2.index;
}

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	vector<pair<int, int>> coordinates;
	int n;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		int t;
		cin >> t;
		coordinates.push_back({ t, i });
	}

	sort(coordinates.begin(), coordinates.end(), cmp_horizon);
    // [](auto& v1, auto& v2) { return v1.horizon < v2.horizon; }); 람다식 가능

	int idx = 0;

	for (int i = 0; i < n - 1; ++i)
	{
		if (coordinates[i].horizon == coordinates[i + 1].horizon)
		{
			coordinates[i].horizon = idx;
		}
		else
		{
			coordinates[i].horizon = idx++;
		}
	}
	coordinates[n - 1].horizon = idx;

	sort(coordinates.begin(), coordinates.end(), cmp_index);
    // [](auto& v1, auto& v2) { return v1.index < v2.index; }); 람다식 가능

	for (auto& data : coordinates)
	{
		cout << data.horizon << " ";
	}

	return 0;
}

cmp_horizon, cmp_index 대신에 람다식을 넣어서 더 짧게 할수도 있다.

다른사람 풀이(46641944) 중에 페어를 쓰지 않고 unique와 lower_bound(=bisect_left)를 이용해서 간결하게 풀어낸 해답이 있다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	vector<string> cant_hear;
	vector<string> cant_see;
	int n, m;
	string s;

	cin >> n >> m;

	while (n--)
	{
		cin >> s;
		cant_hear.push_back(s);
	}
	while (m--)
	{
		cin >> s;
		cant_see.push_back(s);
	}

	// intersection 수행 전 모두 정렬이 되어있어야 함
	sort(cant_hear.begin(), cant_hear.end());
	sort(cant_see.begin(), cant_see.end());

	vector<string> cant_hear_see(cant_hear.size() + cant_see.size());

	// 두 집합 결과의 end iterator가 반환됨
	auto iter = set_intersection(cant_hear.begin(), cant_hear.end(),
    			cant_see.begin(), cant_see.end(), cant_hear_see.begin());
	// 해당 iterator부터 새 컨테이너의 end까지 삭제를 해주면 잉여 크기가 삭제된다
    cant_hear_see.erase(iter, cant_hear_see.end());

	cout << cant_hear_see.size() << '\n';
	for (auto& item : cant_hear_see)
	{
		cout << item << '\n';
	}

	return 0;
}

set의 find 또는 algorithm의 find를 이용하면 intersection을 사용하지 않으므로 컨테이너를 추가로 쓰지 않아도 돼서 메모리를 아낄 수 있다. 코드 가독성도 더 좋아질 것 같다.

from sys import stdin
input = stdin.readline

primeNumber = [1] * 10001

# 에라토스테네스의 체
# n의 최대약수는 sqrt(n) 이하이므로 제곱근+1 까지만 루프를 돈다
for i in range(2, int(10000**0.5)+1):
  if primeNumber[i] == 1:
    for j in range(i*2, 10001, i):
      primeNumber[j] = 0

def goldbach_partition(n):
  # (n/2-a) + (n/2+a) = n
  for i in range(n//2, 0, -1):
    # 차이가 가장 적은 소수판별
    if primeNumber[i] == 1 and primeNumber[n - i] == 1:
      print(i, n-i)
      return
  
for tc in range(int(input())):
  goldbach_partition(int(input()))

처음엔 이중 for문으로 썼다가 당연히 시간초과가 났다. 머리 싸매고 고민해도 답이 안나오길래 질문 게시판에서 힌트란 힌트는 다 훑어보고 난 뒤에서야 수정했다.

어떤 짝수를 두 소수의 합으로 나타낼 수 있다는거 이제 잊고싶어도 못잊을거같다.

n = int(input())

array = [0] * n

for i in range(n):
  array[i] = tuple(map(int, input().split()))

array.sort(key = lambda x: (x[1], x[0]))

end, result = -1, 0

for i in range(n):
  # 현재 진행중인 회의의 종료시간보다 뒤에 있으면서 end가 짧은거 하나만 하면 됨
  # 두가지 조건을 만족해야 하지만 이미 end가 짧은순으로 정렬되어 있기때문에
  # 종료시간 뒤에 있는 가장 가까운 값을 꺼내오기만 하면 end가 짧은게 보장됨
  if array[i][0] >= end:
    end = array[i][1] # 종료시간 갱신
    result += 1

print(result)

얼마전에 공부 했던 내용인데 최적해를 구하는게 한끗차이로 안떠올라서 시간을 좀 잡아먹었다

코드업 4713 이랑 동일한 문제라고 생각해서 코드를 길게 짜다가 조건자체가 더 심플해서 간소화시켰다

근데 지금 생각해보니 코드업 4713도 간소화 시킬수 있을것같은데 일단 보류함

from sys import stdin

t = int(stdin.readline())

for ft in range(t):
  n = int(stdin.readline())
  arr = [0] * n
  
  for i in range(n):
    arr[i] = tuple(map(int, stdin.readline().split()))

  # 첫번째 값 기준으로 오름차순 정렬
  arr.sort() 

  # 1등의 두번째 값을 기준으로 잡고 1등은 무조건 통과이므로 1부터 시작 
  result = 1
  pivot = arr[0][1]
  
  for i in range(1, n):
    if arr[i][1] < pivot:
      result += 1
      pivot = arr[i][1]
      
  print(result)

난이도가 높지 않은 문제는 최적해 구하는 방법에 접근은 잘 하는데 시간이 너무 오래걸린다

그리고 구현할 때 더 단순한 방법이 있음에도 자꾸 어렵게 함

# n일보다 n+1일이 크거나 같으면 구매함
# n일보다 n+1이 작으면 판매함

from sys import stdin

t = int(stdin.readline())

for ft in range(t):
  n = int(stdin.readline())
  arr = [x for x in list(map(int, stdin.readline().split()))]

  stock = 0
  result = 0
  highest = max(arr)
  
  for i in range(n-1):
    if arr[i] <= arr[i+1]:
      stock += 1
      result -= arr[i]
    # 다음날 가격이 떨어지지만 최고가를 만나지 않았으면 팔지 않음
    elif arr[i] > arr[i+1] and arr[i] >= highest:
      result += (arr[i] * stock)
      highest = max(arr[i+1:]) # 최고가 재설정
      stock = 0
    # 전일 등락과 상관없이 최고가를 만나기 전까지는 매수
    else:
      stock += 1
      result -= arr[i]
  # 루프를 한번 덜돌기때문에 마지막날에 대한 결과 처리
  result += (highest * stock)

  print(result)

시간이 9초가 나왔다... 루프 자체는 O(N)인데 아무래도 max를 부르는 횟수가 많아지면 기하급수적으로 늘어나는것 같음

처음 제출했을때 틀리길래 반례를 찾아서 다시 조립했다. 최고가 갱신쪽이 문제였다

2초대가 나온 다른사람 코드를 봤는데 심플했다. 읽어보니 접근 방법은 이해했는데 그런 코드를 작성할 수 있다는게 신기함

count = 1

while True:
  l, p, v = map(int, input().split())

  if l + p + v == 0:
    break
    
  answer = 0
  
  while v >= l:
    v -= p
    answer += l
    
  if v > 0:
    answer += v

  print("Case "+str(count)+": "+str(answer))
  count += 1

코드 짧게 짜놔서 뿌듯했는데 자꾸 오답나길래 보니까 예제출력이랑 동일하게 하는 부분을 처리 안해서 그랬었음

# 0: 갈수있는 곳 1: 벽 2: 먹이
# 계속 오른쪽으로만 가는데 벽이 있으면 한칸 아래로 감

maze = []
x, y = 1, 1
for i in range(10):
  maze.append(list(map(int, input().split())))

dx = (0, 1)
dy = (1, 0)
turn_count = 0

# 첫 위치는 방문처리
maze[x][y] = 9

while True:
  # 회전을 두번 했다면 종료
  if turn_count >= 2:
    break
  
  # 이동할 곳이 벽이 아니라면
  if maze[x+dx[turn_count]][y+dy[turn_count]] == 0:
    x = x + dx[turn_count]
    y = y + dy[turn_count]
    maze[x][y] = 9
    turn_count = 0
  # 이동할 곳이 벽이라면
  elif maze[x+dx[turn_count]][y+dy[turn_count]] == 1:
    turn_count += 1
  # 그 외의 경우는 먹이를 발견했을 때
  else:
    x = x + dx[turn_count]
    y = y + dy[turn_count]
    maze[x][y] = 9
    break

for i in range(10):
  for j in range(10):
    print(maze[i][j], end=' ')
  print("")

a, b = map(int, input().split())
target = abs(a - b)

# 먼저 10으로 나눠준다
result = target // 10
target = target % 10


if target in [1, 5]: # 1: +1 / 5: +5
  result += 1
elif target in [2, 4, 6, 9]: # 2: +1,+1 / 4: 5,-1 / 6: 5,+1 / 9: +10,-1
  result += 2
elif target in [3, 7, 8]: # 3: +1,+1,+1 / 7: +5,+1,+1 / 8: +10,-1,-1
  result += 3

print(result)

쓸데없이 생각을 너무 복잡하고 길게 하는것 같다. 최적해를 찾기 위해 생각을 단순화 시킬 필요가 있다

고작 이거하나 짜는데 1시간이 걸렸다

t = int(input())
dPrice, tPrice = map(int, input().split())
dCalorie = int(input())

tCalorie = []
for i in range(t):
  tCalorie.append(int(input()))
  
# cpd의 효율을 위해 내림차순 정렬
tCalorie.sort(reverse=True)

totalCalorie = dCalorie
totalPrice = dPrice
cpd = totalCalorie // totalPrice # calorie per dollar

for x in tCalorie:
  # 토핑의 cpd가 전체 cpd보다 높으면 토핑 추가
  if (x // tPrice) > cpd:
    totalCalorie += x
    totalPrice += tPrice
    cpd = totalCalorie // totalPrice
  # 오름차순 정렬이기때문에 한번만 만족하지 못해도 루프 탈출
  else:
    break

print(format(cpd,".0f"))

접근은 거의 다 했는데 누적 평균값을 고려하지 않아서 조금 헤맸음

from sys import stdin

period, r = map(int, stdin.readline().split())

schedule = [0] * period

for i in range(0, period):
  schedule[i] = (list(map(str, stdin.readline().rstrip())))

start, end = map(int, stdin.readline().split())
start -= 1 # 인덱스 접근을 편하게 하기위해 감소
end -= 1
changeCount = -1

while start < end:
  maxDay = 0
  
  for i in range(r):
    count = 0
    for j in range(start, end):
      # 빈방을 발견하면 계속 확인함
      if schedule[j][i] in 'O':
        count += 1
      else:
        break
    # 최대 숙박 가능일
    if maxDay < count:
      maxDay = count

  # 숙박 가능일이 0이 아니면 방이 있음
  if maxDay != 0:
    start += maxDay
    changeCount += 1
  # 숙박 가능일이 0이면 예약이 다 찬상태
  else:
    changeCount = -1
    break

print(changeCount)

시간초과가 계속 뜨길래 입력방법도 바꿔보고 했다가 뒤늦게 안 사실은 마지막에 break 하나를 안넣어서 루프탈출을 못해서 그런거였다. 그걸 못찾고 계속 코드 다듬다가 30분이 갔다

이번에는 충분히 할 수 있는데도 '이 방법은 아니지 않을까?' 하면서 고민을 너무 오래했다

최대 숙박 가능일들을 뽑아서 방 번호와 튜플로 묶어서 리스트에 보관하는 뻘짓을 했었는데 조금 생각해보니 그런 데이터를 보관할 필요가 없다는걸 깨닫고 다 날려버림

# [0]시작월 [1]시작일 [2]종료월 [3]종료일

# 3/1 ~ 11/30
# 1. 시작일(초기3/1) 이하 꽃중에 가장 늦게까지 피는 꽃 선택
# 2. 해당 꽃 종료일 이하 꽃중에 현재 종료일보다 더 뒤쪽으로 가장 늦게까지 피는 꽃 선택
# 만약 선택할 수 없다면 0 반환후 즉시 종료
# 매 선택마다 11/30이 초과되는지 확인해야한다
# 선택된 꽃 카운팅 해서 출력

n = int(input())

array = [0] * n
for i in range(n):
  array[i] = list(map(int, input().split()))

# 시작월일 기준으로 정렬
array.sort(key = lambda x: (x[0], x[1]))

index, result = 0, 0
start = [3, 1]
end = [11, 30]

longFlower = array[0]
while True:
  count = 0
  for i in range(index, n):
    # 시작일보다 아래에 있는 꽃 탐색
    if (array[i][0] < start[0]) or (array[i][0] <= start[0] and array[i][1] <= start[1]):
      # 가장 늦게까지 피는 꽃 탐색
      longFlower = max(longFlower, array[i], key = lambda x: (x[2], x[3]))
      count += 1
      index = i + 1 # 루프 횟수를 줄이기 위한 변수
    else:
      break

  # 시작 날짜를 꽃의 끝나는 날로 재지정
  start[0], start[1] = longFlower[2], longFlower[3]
  result += 1

  # 조건을 만족한 경우 루프 탈출
  if start[0] > end[0]:
      break
  # 조건을 하나도 찾지 못한경우 경우의 수가 없음
  elif count == 0:
    result = 0
    break

print(result)

220719 solved

뭔가.. 뭔가 좀 깔끔하지 않은 것 같은데 아무튼 풀었음

처음에 주석으로 워크플로우 대충 구상해놓고 하니까 수월했음

from collections import deque

n = int(input())

def bfs(pivot, start):
  queue = deque([start])

  while queue:
    val = queue.popleft()

    # 최대 범위보다 크면 루프 종료
    if val >= 2**64:
      return 0
    # 나누어지면 공배수라는 뜻
    elif val % pivot == 0:
      return val

    # 큐에 값 추가. 그림으로 그리면 이진트리와 비슷한 그림이 그려짐
    queue.append(val * 10)
    queue.append(val * 10 + 1)

print(bfs(n, 1))

220716 solved

BFS 이용. 이상하게 문제 이해가 오래걸려서 풀이를 좀 찾아본 뒤에서야 이해했음

# 2605 캔디팡 220715

width, height = 7, 7

graph = []
for i in range(height):
  graph.append(list(map(int, input().split())))

# 7x7 리스트 초기화
visited = [[False] * width for _ in range(height)]

count = 0

def dfs(x, y, color):
  global count
  
  if x <= -1 or x >= width or y <= -1 or y >= height:
    return False

  # 방문하지 않음과 동시에 같은 색상인것만 골라서 방문처리
  if visited[x][y] == False and graph[x][y] == color:
    visited[x][y] = True
    count += 1
    dfs(x+1, y, color)
    dfs(x-1, y, color)
    dfs(x, y+1, color)
    dfs(x, y-1, color)
    return True

  return False

result = 0

for i in range(width):
  for j in range(height):
    dfs(i, j, graph[i][j])
    # 3개 이상의 색이 연달아 있는 경우만 카운팅
    if count >= 3:
      result += 1
    count = 0

print(result)

220715 solved

DFS 이용

# _: 색칠되지 않은 부분, *: 색칠된 부분

paint = []
for i in range(10):
  paint.append(list(input()))

x, y = map(int, input().split())

def dfs(array, _x, _y):
  if _x <= -1 or _x >= 10 or _y <= -1 or _y >= 10:
    return

  # 보통 인지하는 x,y와 배열의 행렬은 반대이므로 바꿔서 사용
  if array[_y][_x] == '_':
    array[_y][_x] = '*'
    dfs(array, _x+1, _y)
    dfs(array, _x-1, _y)
    dfs(array, _x, _y+1)
    dfs(array, _x, _y-1)
  else:
    return

dfs(paint, x, y)

for i in range(10):
  for j in range(10):
    print(paint[i][j], end='')
  print("")

220716 solved

일반적인 DFS. visited 처리를 따로 안해도 됨

from queue import PriorityQueue

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

graph = [[0] for _ in range(v+1)]
indegree = [0] * (v+1)
p_queue = PriorityQueue()

for i in range(n):
  x, y = input().split()
  x, y = int(x), int(y)
  graph[x].append(y)
  indegree[y] += 1

for i in range(1, v+1):
  if indegree[i] == 0:
    p_queue.put(-i)

while not p_queue.empty():
  here = -p_queue.get()
  print(here)

  for i in graph[here]:
    indegree[i] -= 1
    if indegree[i] == 0:
      p_queue.put(-i)

정답은 이건데 솔직히 봐도 아직 모르겠음

삽질의 기록들

# v: 정점의 개수 n: 간선의 개수. 인덱스는 둘다 1부터 쓸것

from queue import PriorityQueue

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

# 열n+1 행v+1. 행 인덱스 0은 버릴거기때문에 v만 한개 더 크게
# 앞쪽이 가로길이(열/간선), 뒤쪽이 세로길이(행/정점)
graph = [[0] for _ in range(v+1)]

# 탐색 시작 노드를 저장할 변수
init_v = 0

for i in range(n):
  x, y = input().split()  
  graph[int(x)].append(int(y))
  if i == 0:
    init_v = int(x)
    
result = []

def dfs(array, start, visited):
  # 우선순위 큐 사용 선언
  p_queue = PriorityQueue()
  p_queue.put(start)
  visited[start] = True

  # 큐가 빌때까지
  while not p_queue.empty():
    v = p_queue.get() 
    # 우선순위 큐를 통해 나온 값은 언제나 최소값과 중복이 아님을 보장받는다
    result.append(v)

    for i in range(1, len(array[v])):
      if not visited[array[v][i]]:
        p_queue.put(array[v][i])
        visited[array[v][i]] = True
        
  return

# 방문을 체크하는 리스트
visitedCheck = [False] * (v+1)

dfs(graph, init_v, visitedCheck)

# 주어진 노드 개수만큼 들어가지 않았다면 탐색을 실패했다는 소리
# 애초에 중복은 우선순위 큐에 들어가지 않으니 순회인지, 끊긴건지는 알 수 없음
if len(result) <= v-1:
  print(-1)
else:
  for i in range(len(result)):
    print(result[i])

반례를 보니 우선순위 큐로 풀리네? 해서 짜놨더니 막히고 다음 반례를 확인하니까 아니었음

여전히 헤메고 있는중