say repository

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

출처 : 백준

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

import sys
n = int(sys.stdin.readline())
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
graph = [[0]*101 for _ in range(101)]

for i in range(n):
    x, y, d, g = map(int,sys.stdin.readline().split())
    graph[x][y] = 1

# 커브 변화 배열 만들기
    curv = [d]
    for ge in range(g):
        for c in range(len(curv)-1, -1, -1):
            curv.append((curv[c]+1) % 4)
            
# 드래곤 커브 돌면서 방문 표시
    for i in range(len(curv)):
        x += dx[curv[i]]
        y += dy[curv[i]]
        if 0 <= x <= 100 and 0 <= y <= 100:
            graph[x][y] = 1

# 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브인 경우 개수
answer = 0
for i in range(100):
    for j in range(100):
        if graph[i][j] == 1 and graph[i+1][j] == 1 and graph[i][j+1]==1 and graph[i+1][j+1]==1:
            answer += 1
print(answer)

풀이

시작 방향 d를 보면

0 (1, 0)

1 (0, -1)

2 (-1, 0)

3 (0, 1)

다음과 같다.

세대 별로 방향의 변동의 규칙을 찾아보면 위의 그림과 같다.

인접한 방향 배열에서 1을 더하는 것이다.

코드

import sys

n = int(sys.stdin.readline())
answer = 0
for i in range(1,n+1):
    answer += (n//i) *i
print(answer)

풀이

바로 생각해내기 어려웠다.

2의 배수를 생각해보자.

2, 4, 6, 8, ... 당연히 2의 배수니까 모든 배수에 2가 포함되어 있다. 

n이 4라면 4//2 = 2  -> 2가 2번 있다.

n이 8라면 8//2 = 4 -> 2가 4번 있다.

.... 

i 가 n // i 번 있다는 것이다.

그래서  아래와 같이 코드를 작성했다.

answer += (n//i) *i

출처 : 백준

import sys
n = int(sys.stdin.readline())
cnt = 0
for i in range(n):
    s = sys.stdin.readline().rstrip()
    new_word = [s[0]]
    err = 0
    for a in range(len(s)-1):
        if s[a] != s[a+1]:
            if s[a+1] in new_word:
                err += 1
            new_word.append(s[a+1])

    if err == 0:
        cnt += 1
print(cnt)

풀이

입력받은 문자열을 한 글자씩 비교하면서 다른 글자가 나오면 new_word에 넣는다.

이때, new_word에 있는 글자라면 그룹 단어가 되지 않으니 체크한다.

출처 : 백준

# 10972
import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
x = 0
for i in range(n-1, 0, -1):
    if arr[i] > arr[i-1]:
        x = i-1
        break
for i in range(n-1, 0, -1):
    if arr[x] < arr[i]:
        arr[x], arr[i] = arr[i], arr[x]
        arr = arr[:x+1] + sorted(arr[x+1:])
        print(*arr)
        exit()
print(-1)

풀이

 next_permutation

1. 순열의 뒤 부터 비교하며 뒷 값이 앞 값 보다 큰 인덱스 구해서 x에 앞 값 인덱스 넣기
2. 이 x 값과 다시 순열의 뒤부터 비교해서 arr[x] 보다 큰 값 구하고 swap 진행하기
3. x 다음 값이 큰 값이었다.
4. 이 값 기준으로 앞은 그대로, 뒤는 sorted 해서 포인트로 접근 print()
5. exit() 종료

# 1476

import sys
e, s, m = map(int,sys.stdin.readline().split())
cnt = 1
starte, starts, startm = 1,1,1
while True:
    if starte == e and starts == s and startm == m:
        break
    starte += 1
    starts += 1
    startm += 1
    cnt += 1
    if starte > 15:
        starte = 1
    if starts > 28:
        starts = 1
    if startm > 19:
        startm = 1

print(cnt)

풀이

1 1 1 을 1년 지날 때마다 모두 +1 해주며 e, s, m 값과 같아질 때까지 cnt+=1 해준다.

+1 해줄 때, e,s,m 의 범위 넘으면 다시 1로 초기화해준다.

# 3085

import sys
n = int(sys.stdin.readline())
arr = [list(sys.stdin.readline().strip()) for _ in range(n)]
answer = 0

# 완전 탐색
def check(array):
    max_len = 1 # 함수의 리턴 값 -> 가장 긴 최대 길이
    for i in range(n):
        # 열 비교
        cnt = 1 # 같은 색인 최대 길이
        for j in range(1,n):
            if arr[i][j] == arr[i][j-1]:
                cnt += 1
            else: # 인접한 사탕 중 다른 색 나오면 cnt 초기화
                cnt = 1
            max_len = max(max_len, cnt) # max_len 갱신
        
        # 행 비교
        cnt = 1  # 같은 색인 최대 길이
        for j in range(1,n):
            if arr[j][i] == arr[j-1][i]:
                cnt += 1
            else:
                cnt = 1
            max_len = max(max_len, cnt)  # max_len 갱신
    return max_len

# 인접하고 색 다른 두 칸 고르고 완탐 호출
for i in range(n):
    for j in range(n):
        if j+1<n: # 인접한 열 끼리 비교 후 교체
            if arr[i][j] != arr[i][j+1]:
                arr[i][j],arr[i][j+1] = arr[i][j+1], arr[i][j]
                # 완전탐색 수행
                tmp = check(arr)
                # 정답과 완탐 CNT 비교
                answer = max(answer,tmp)
                # 교체 한 것 다시 원래대로 돌려놓기 ( 모든 경우의수 비교해야함)
                arr[i][j], arr[i][j + 1] = arr[i][j + 1], arr[i][j]

        if i+1<n: # 인접한 행 끼리 비교 후 교체
            if arr[i][j] != arr[i+1][j]:
                arr[i][j], arr[i + 1][j] = arr[i + 1][j],arr[i][j]
                # 완전탐색 수행
                tmp = check(arr)
                # 정답과 완탐 CNT 비교
                answer = max(answer, tmp)
                # 교체 한 것 다시 원래대로 돌려놓기 ( 모든 경우의수 비교해야함)
                arr[i][j], arr[i + 1][j] = arr[i + 1][j], arr[i][j]
print(answer)

풀이

보드의 크기 N이 주어진다. (3 ≤ N ≤ 50) -> 완전 탐색 가능하다.

1. 색이 다른 인접한 두 사탕 선택 후 교체

2. 교체한 배열에서 같은 사탕 색이 있는 (행 또는 열) 최대 길이 구하기

3. 교체한 사탕 다시 제자리로 위치시키고 다음 인접한 사탕 교체 후 완전탐색 반복

계속 교체할 사탕 2개 선택해서 자리 바꾸고 완탐으로 최대 길이 구하고 리턴 시켜서

answer 값을 max 값으로 갱신시킨다.

이 문제 괜찮은 것 같다.

나중에 다시 풀어보자.

# 11724
import sys
sys.setrecursionlimit(10000)
n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
cnt = 0
for _ in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
# print(graph)

def dfs(node):
    visited[node] = 1
    for i in graph[node]:
        if not visited[i]:
            dfs(i)

for i in range(1,n+1):
    if not visited[i]:
        dfs(i)
        cnt += 1
print(cnt)

풀이 2 (BFS)

# 11724
import sys
# sys.setrecursionlimit(10000)
from collections import deque
n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
cnt = 0
for _ in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
# print(graph)

def bfs(graph, node, visited):
    visited[node] = 1
    q = deque([node])
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = 1

for i in range(1,n+1):
    if not visited[i]:
        bfs(graph, i, visited)
        cnt += 1
print(cnt)