문제https://www.acmicpc.net/problem/9470문제 설명하천계는 유향그래프로 나타낼 수 있다.강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다.노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳, 바다와 만나는 곳네모 안의 숫자는 Strahler 순서를 나타내고 동그라미 안의 숫자는 노드 번호를 나타낸다.강의 근원인 노드의 순서는 1이다.나머지 노드는 그 노드로 들어오는 강의 Strahler 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강의 1개면 순서는 i, 2개 이상이면 순서는 i+1이다.하천계의 순서는 바다와 만나는 노드의 순서와 같다. 바다와 만나는 노드(K번이 항상 바다와 만나는 노드이다.)..

문제https://www.acmicpc.net/problem/20209문제 설명N개의 큐브, 그리고 일부 큐브와 연결되어 있는 K개의 스위치가 존재한다.i번 스위치를 누르면 연결된 모든 큐브의 숫자가 각각 i 만큼 증가한다.큐브 위에는 0,1,2,3,4만 존재하며, 4를 초과할 경우 5로 나눈 나머지로 즉시 초기화된다.스위치를 한 번 누를 때, 반드시 단 한 개의 스위치만 누를 수 있다.같은 번호의 큐브가 한 스위치에 여러 번 연결되어 있는 경우는 없다.스위치를 누를 수 있는 횟수의 제한은 없다.큐브 위에 쓰여 있는 모든 숫자가 동일해지는 순간, 게임은 종료된다.눌러야 하는 스위치의 최소 횟수를 구한다. 풀이BFS를 통해서 문제를 해결했다. 이 문제의 핵심은 "주어진 값을 이용해서 어떻게 그래프로 변형..

문제https://www.acmicpc.net/problem/1011문제 설명공간이동 장치를 통해 x지점에서 y지점으로 이동을 하려고 한다.공간이동 장치는 이동 조건이 있다.이동 거리는 0부터 시작해서 이전 이동거리가 k라면 다음 이동은 k-1, k, k+1만 이동이 가능하다.y지점에 도착하기 전 마지막 지점에서는 1의 거리로 이동해야 한다.x지점에서 y지점으로 정확히 이동하는데 필요한 장치의 최소 작동 횟수를 구해라. 풀이처음에는 그래프 탐색 혹은 DP로 접근하는 문제인가?라고 생각했다. 결국에는 앞으로만 전진하기 때문이다. 하지만 x와 y의 범위가 $2^{31} = 10^9$정도이기 때문에 말도 안 된다고 생각하고 다른 방법은 고안했다. 일단 시작지점과 마지막 지점은 1이라는 힌트가 주어졌기 때문에 ..

문제https://www.acmicpc.net/problem/32985문제 설명0번부터 N-1번까지 N개의 노드를 가진 트리가 주어진다.두 노드 u, v에 대하여 c(u,v)를 다음과 같이 정의한다.$f(x) = (c(x,N-1)c(x,N-2)...c(x,1))_{(2)}$이 때 $f(1)$ ⊕ $f(2)$ ⊕ $f(3)$... ⊕ $f(N-1)$의 값을 구한다. 풀이문제를 읽었을 때 XOR 비트를 구하는 거니까 당연히 비트마스킹을 쓰는 줄 알았다. 그런데 비트마스킹으로 풀려고 하다 보니 뭔가 시원하게 풀리지 않아서 예제 하나를 나열하고 하나의 규칙을 찾았다.60 11 20 33 43 5 해당 예제에서 모든 경우의 수를 아래의 표에 전부 나열했다.f(1,5) = 1f(2,5) = 1f(3,5) = ..

문제https://www.acmicpc.net/problem/3095문제 설명0과 1로 이루어진 N*N 행렬이 주어진다.행렬에 플러스가 몇 개가 존재하는지 구해야 한다.플러스는 변의 길이가 1보다 큰 홀수인 정사각형이다.가운데 행과 열은 1로, 나머지는 0으로 이루어져 있다. 풀이단순 브루트포스 문제라 쉬울거라고 예상했는데, 시간초과가 발생해서 코드를 최적화 하느라 문제 풀이 시간이 좀 더 지연됐다. N의 최대 크기는 2000이기 때문에 브루트포스로 충분히 풀이가 가능하다고 생각하고 빠르게 코드를 작성했다.import sysinput = sys.stdin.readlineN = int(input())board = [list(map(int,input().strip())) for _ in range(N)]dr..

문제https://www.acmicpc.net/problem/5972문제 설명$N$개의 헛간과, 소들의 길인 $M$개의 양방향 길이 그려져 있다.각각의 길은 $C_i$마리의 소가 있다.소들의 길은 두 개의 떨어진 헛간인 $A_i$와 $B_i$를 잇는다.두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있다.농부 현서는 헛간 1에 있고 찬홍이는 헛간 N에 있다.현서가 찬홍이에게 택배를 배송해주면서 지나가는 길에는 소들에게 여물을 줘야한다.여물을 최소로 주면서 이동했을 때 최소 여물을 구한다. 풀이정말 전형적인 다익스트라 문제이다. 다익스트라의 기본 구현은 항상 비슷하다. 문제에서 주어진 노드 간 cost를 graph를 통해 초기화한다.dist 배열을 통해 현재 노드까지의 총 cost를 갱신한다. (초기..

문제https://www.acmicpc.net/problem/1584문제 설명 위험한 지역에서 탈출하는 게임을 해야한다. 이 게임에는 세 가지 구역이 존재한다.들어갈 수 없는 죽음의 구역한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역자유롭게 움직일 수 있는 안전한 구역이 때 시작점은 (0,0)이고 도착점은 (500,500)이다. 이동 방향은 상, 하, 좌, 우로 이동할 수 있다. (게임판은 벗어날 수 없다.)(0,0)에서 (500,500)으로 갈 때 잃는 생명의 최솟값을 구해라.주어지는 구역은 모두 겹칠 수 있으며, 서로 다른 구역이 겹칠 때는, 더 심한 구역이 해당된다. 예를 들어, 죽음+위험 = 죽음, 위험+안전 = 위험, 위험+위험 = 위험, 죽음+안전 = 죽음이다. 풀이보통 그래프로 문..

문제https://www.acmicpc.net/problem/1041문제 설명주사위의 전개도의 각 면에는 수가 쓰여져 있다.(A,B,C,D,E,F)동일한 주사위를 $N^3$개 가지고 있을 때 적절하게 회전하고 쌓아서 $N^3$크기의 정육면체를 만들려고 한다.이 때 정육면체는 탁자위에 있으므로 5개의 면만 보인다.N과 주사위의 수가 주어졌을 때 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력해라. 풀이문제를 처음 봤을 때는 단순하게 접근했다.보이는 면은 총 5개, 그중 대칭되는 면 2개, 2개 윗면 1개로 구성되어 있기 때문에 주사위를 배치할 수 있는 모든 경우의 수를 구해서 그중 가장 합이 낮은 숫자를 선택하기로 했다. 2x2x2 정육면체 그림으로 예시를 들어보자.(그림은 알지오매스라는 사이트를 이용했다..

문제https://www.acmicpc.net/problem/31462문제 설명정육각형 3개를 삼각형 모양으로 붙인 초콜릿을 판매하려고 한다.같은 크기의 정육각형 $N(N+1)/2$개를 삼각형 모양으로 붙인 형태의 틀에 이 초콜릿들을 넣어 포장하려고 한다.위로 뾰족한 방향으로 배치된 초콜릿은 빨간색, 반대 방향의 초콜릿은 파란색으로 개별 포장한다.완성된 상품이 제대로 포장되었는지 판별한다. 풀이위로 뾰족한 방향으로 배치된 초콜릿은 빨간색, 반대 방향의 초콜릿은 파란색으로 개별 포장한다.-> 이 말이 무슨 의미인지부터 이해해 보자.문제에 나와있는 예시 이미지이다. R은 빨간색, B는 파란색 초콜릿이다.R은 위가 뾰족한 형태, B는 아래가 뾰족한 형태의 삼각형을 이루기 때문에 이러한 구조가 반복되어 포장되어..

문제https://www.acmicpc.net/problem/1469문제 설명숌은 N개의 서로 다른 숫자로 구성되어 있는 집합 X이다.이를 통해 2N 길이의 숌 사이 수열 S를 만들어야 한다.X에 들어있는 모든 수는 숌 사이 수열 S에 두 번 등장해야 한다.X에 등장하는 수가 i라면 S에서 두 번 등장하는 i사이에는 i개의 수가 등장해야 한다.숌 사이 수열은 사전 순으로 가장 빠른 것을 출력하고, 없을 경우 -1을 출력한다. 풀이첫번째 예제를 통해 문제를 이해해보자.31 2 3위와 같은 예제가 주어졌을 때1 사이에는 1개의 숫자, 2 사이에는 2개, 3 사이에는 3개의 숫자가 들어가야 한다. 하나의 예시를 들어보면 2 3 1 2 1 3과 같다. 각 숫자 사이에는 숫자의 개수만큼의 수가 들어가 있다. 이 ..