FFTL

1806번: 부분합첫째 줄에 N (10 ≤ N www.acmicpc.net문제 간단 설명 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.문제 풀이 저는 사실 이 문제를 읽고나서 이 문제가 DP 문제인지, 세그먼트 트리? 를 이용하여 풀어야 하는지 가늠이 가지 않았습니다. 그래서 해당 문제의 알고리즘 분류를 읽어보았고 투 포인터 문제라는 것을 알게 되었고 이를 이용하여 문제를 풀기 시작했습니다. 아마 이를 알지 못했다면 문제를 푸는데 더 오랜 시간이 걸렸을 것이라 생각합니다. 배열의 시작 인덱스, 종료 인덱스를 각각 놓고 종료 인덱스를 증가시켜 나가며 부분의 합..

2251번: 물통각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부www.acmicpc.net문제 간단 설명 A, B, C 각각 세 개의 물통이 주어집니다. 그리고 최초에 C 물통에는 물이 가득 차있으며 이 물통의 물을 각각 다른 물통으로 옮길 수 있습니다. 다만 물을 옮길 때, 받는 대상이 가득 차던지, 주는 대상이 비워지든지 해야합니다. 이렇게 계속해서 물을 옮길 때, A 물통이 비어있을 때, C 물통에 담겨있을 수 있는 물의 양을 모두 구하는 문제입니다. 문제 풀이 저는 아무래도 물통이 세 개 뿐이다 보니, 모든 경우의 수를 확인하는..

15684번: 사다리 조작사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선www.acmicpc.net문제 간단 설명 배열의 형태로 세로선과 그 세로선 사이를 있는 사다리가 몇 개 주어집니다. 그리고 사용자는 임의의 위치에 가로선을 추가 할 수 있는데 이 작업을 통해서 모든 사다리가 출발과 도착을 같은 세로선에서 하도록 만드는 문제입니다.문제 풀이 저는 사다리의 최대 크기가 30 X 10 이라는 것과 추가할 수 있는 최대 가로선의 개수가 3개라는 것을 보고 완전 탐색을 생각했습니다. 그리하여 1~3개의 사다리를 놓았을 때의 모든 경우의 수를 구했고, 각각의 세로선이 ..

15683번: 감시스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감www.acmicpc.net문제 간단 설명 보드가 주어지고 보드 안에 벽과 카메라가 주어집니다. 카메라는 5가지 종류가 있으며 볼 수 있는 방향이 각각 다릅니다. 그리고 이 카메라는 얼마든 회전시킬 수 있습니다. 주어진 카메라들을 마음대로 회전한 뒤 가장 많은 곳을 볼 수 있는 즉 사각지대가 가장 적게 되었을 때의 사각지대의 개수를 구하는 문제입니다. 문제 풀이  카메라의 최대 개수가 8개이기 때문에 충분히 작은 수라고 판단했습니다. 그렇기에 모든 경우의 수를 확인하는 dfs를 이용해..

21608번: 상어 초등학교상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호www.acmicpc.net 문제 간단 설명 상어 초등학교에서 자리 배치를 진행합니다. 이 때 입력되는 학생 순서대로 자리를 배치하며 각 학생이 좋아하는 학생들이 많이 인접한 자리로 배치해주려 노력합니다. 만약 그 수가 같다면 인접한 자리에 빈자리가 많아야 하고, 그 마저도 같다면 가장 좌상단의 자리를 배치해줍니다. 그리고 결과적으로 각각의 학생들이 얼마나 만족하는지 구하는 문제입니다.문제 풀이 / 코드 코드의 주석으로 문제의 풀이를 대체합니다.package com.baekjoon.g..

14891번: 톱니바퀴총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴www.acmicpc.net문제 간단 설명 네 개의 톱니바퀴가 존재하며 각 톱니바퀴를 회전시킵니다. 톱니바퀴가 회전할 때 인접한 곳에 있는 톱니바퀴와 만나는 부분의 자석 극이 다르다면 함께 회전하게 됩니다. 톱니바퀴를 여러 번 회전 시킨 후 톱니바퀴의 상태를 확인하는 문제입니다.문제 풀이 이번 문제도 구현 문제로 톱니바퀴의 모양을 어떻게 코드로 표현하며, 이를 어떻게 회전시키는지 생각할 수 있는지 보는 문제 입니다.코드package com.baekjoon.gold;import java.io...

14888번: 연산자 끼워넣기첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net문제 간단 설명 주어진 수와 주어진 연산자의 개수를 가지고 구할 수 있는 최댓값, 최솟값을 구하는 문제입니다. 주어진 수의 배치는 변경할 수 없으며, 연산은 무조건 왼쪽부터 시행한다는 조건이 가지고 있어 그렇게 어려워 보이지는 않는 문제였습니다.문제 풀이 저는 dfs를 이용하여 풀어보았습니다. 생각을 떠오르기 전에는 뭔가 힘들었는데 dfs로 풀면 되겠다라고 떠오르고 나니 생각보다 쉽게 해결을 한 문제입니다. 사실..

14503번: 로봇 청소기첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽www.acmicpc.net문제 간단 설명 보드가 주어지고 로봇청소기가 이동하며 먼지를 청소합니다. 몇칸의 먼지를 청소 할 수 있는치 카운트 하는 문제입니다.문제 풀이 특별한 알고리즘이 필요하다기 보다는 문제에서 주어진 대로 구현하는 문제입니다. 보드 안에서 네 방향의 탐색을 할 수 있다면 풀 수 있는 문제입니다.코드package com.baekjoon.gold;import java.io.BufferedReader;import java.io.I..

14499번: 주사위 굴리기첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지www.acmicpc.net문제 간단 설명 각 면에 숫자를 가진 주사위가 보드를 이동하며 숫자들을 변경합니다. 이 때 주사위가 이동할 때마다 주사위의 상단에 있는 숫자를 출력해야합니다.문제 풀이 특별한 알고리즘이 필요한 문제는 아니었습니다. 주사위의 이동을 어떻게 표현할지 생각할 수 있다면 풀 수 있는 백준의 골드 난이도 치고는 쉬운 문제라고 생각합니다. 코드package com.baekjoon.gold;import java.io..

2096번: 내려가기첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.www.acmicpc.net문제 간단 설명세로 길이 N 가로길이 3을 가진 표가 존재하며 각 층마다 세 개의 수가 존재합니다. 각 세 개의 수는 그 다음 층(아래층)으로 내려갈 때에 바로 아래 또는 바로 아래의 수와 붙어있는 수로만 이동할 수 있습니다.별표는 현재 위치, 그리고 파란 동그라미가 갈 수 있는 위치 입니다. 그렇다면 숫자 표가 주어졌을 때 가장 아래층에 도달 할 수 있는 최대수, 최소수를 구하시오.문제 풀이저는 DP를 이용해 푸는 방식을 생각했습니다. 각 위치별로 갈 수 있는 위치가 정해져 있으..