초콜릿 파워

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 랭크 : 골드 4 걸린 시간: 40분 해설 이 문제는 치즈가 시간이 지날 때마다 공기와 닿는 부분이 녹는 문제이다. 쉽게 생각하면 자칫 할 수 있는 오류는 다음과 같다. "공기를 queue에 담은 후 BFS를 진행하면서 시간(== 닿는데 걸린 거리)을 체크하면 되지 않을까? " 이러한 점은 문제가 다음과 같다. 1. 치즈 안의 공기, 즉 가장 자리와 맞닿아 있지 않은 공기는 치즈를 녹이지 않는다. 2. 새로 생긴 구..

https://www.acmicpc.net/problem/3190 난이도 골드4 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지..

https://www.acmicpc.net/problem/1041 문제 +---+ | D | +---+---+---+---+ | E | A | B | F | +---+---+---+---+ | C | +---+ 주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다. A, B, C, D, E, F에 쓰여 있는 수가 주어진다. 지민이는 현재 동일한 주사위를 N3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다. N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오. 그림에서 파란색으..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 ..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열이라는 이름에 걸맞게 투 포인터 알고리즘일 거라고 생각해서 풀이했으나, 문제점을 발견했다. 그 사례는 다음과 같다. 5 3 1 1 1 1 1 이 경우 답은 5Combination(3) = 10인데도 답이 5가 나오는 문제였다. 생각해본 결과 이건 앞으로만 가면서 세기 때문에 중복된 숫자가 있을 경우 각각의 조합의 경우의 수를 찾기가 어렵다는 판단이 들었다..

https://www.acmicpc.net/problem/1644 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구..

무게 제한이 더 큰 크레인이 더 무거운 물건을 드는 것이 유리하다. 그리디라는 것을 검증하기 위해 다음과 같은 과정을 거쳤다. - 무게 제한이 더 작은 크레인이 무게가 무거운 물건을 들었을 때의 정답이 있다. -> 무게제한이 더 큰 크레인이 그 물건을 들어도 정답이 될 수 있으므로, 합당하다. 부분구조가 가능하기 때문에 전체 구조가 가능하다는 논리하에 검증한 것이다. 위를 구현하기 위해 크레인의 무게 제한, 물건의 무게를 내림차순으로 정렬한뒤, 크레인이 물건을 순회하면서 들 수 있도록 했다. 다만, 크레인들은 무게가 무거운 물건은 스킵하되 더 가벼운 물건을 들 수 있도록 해서 전체 크레인이 최대한으로 물건을 들 수 있도록 했다. 크레인이 운반을 못하는 edge case는 무게 제한이 가장 큰 크레인이 무..

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다. 예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다. 시추관은 위 그림처럼 설치한 위치 아래..

https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 난이도: SILVER 1 java로 알고리즘을 푸는 것을 도전중이다. static main에 대해 모든 걸 static 으로 구현하는 점, input,output이 다른 점 등이 색다르다. 이번 문제는 접두사 부분집합의 최대개수를 다루는 문제이다. 해당 접두사들은 대표 접두사만 저장하고, 해당 접두사를 포함하는 문자열이라면 그냥 지나가는게..

교차점은 가로선과 세로선이 겹쳐서 만들어진다. 세로선, 가로선끼리는 서로 겹치지 않게 만들어지기 때문에, 세로선과 가로선이 서로 얼마나 겹치는 지에 따라 교차점의 개수가 달라진다. 예제1을 보면 아래 코드에서 주석처리된 표를 보면, 가로와 세로를 저장하는 배열을 만들어두었다가, 이 둘의 곱의 전체 합을 구하면 답이 된다. 초기 상태가 0이기 때문에, 교차하지 않는 경우엔 자동으로 0을 더하는 꼴이 되어 문제가 없다. 정답을 보자! #include using namespace std; long long garo[101][101] = {0,}; long long sero[101][101] = {0,}; long long N, M; long long ans= 0; /* 1 2 3 1 2 3 1 2 3 가로 :..