본문 바로가기

문제 노트/백준

 (102)
What's Up With Gravity( BOJ 5827 ) 문제 : https://www.acmicpc.net/problem/5827 5827번: What's Up With Gravity Output Details The captain starts at position (4, 2). She flips gravity and falls to position (2, 2) and then moves right twice to arrive at (2, 4). She flips gravity again and falls to position (4, 4) and then moves right once to position (4, 5). Finally www.acmicpc.net 문제 파악하기 N*M 형태의 2차원 맵에서 C 위치에 있는 캡틴 Bovidian가 목적지 D까지 ..
Contact( BOJ 1013 ) 문제 : https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 문제 파악하기 주어진 N개의 문자열이 각각 (100+1+ | 01)+ 을 만족하는지 확인하는 문제입니다. 라이브러리 함수를 사용하거나 오토마타를 사용하는 방법도 있지만, 여기에서는 반복문과 문자열만을 사용하여 문제를 해결해보겠습니다. 문제 해결하기 문자열을 탐색할 때에는 현재 어떤 문자열 형식을 확인하고 있는지 파악하는 것이 중요합니다. 우리는 "100+1+" 형식과 "01" ..
네온 사인( BOJ 8907 ) 문제 : https://www.acmicpc.net/problem/8907 8907번: 네온 사인 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 꼭짓점의 개수 N(3 ≤ N ≤ 1,000)이 주어진다. 다음 N-1개의 각 야광 튜브의 색이 주어진다. 이 줄의 i번째 줄에는 꼭 www.acmicpc.net 문제 파악하기 N개의 꼭지점 중 3개의 꼭지점을 골라 삼각형을 만들었을 때, 모든 간선의 색이 동일한 경우의 수를 구하는 문제입니다. N이 최대 1,000이기 때문에 처음 보면 크지 않아 보이지만, 1000개의 정점 중 3개의 정점을 선택할 수 있는 경우의 수는 대략 1.6억 가지 경우의 수가 있습니다. 어마어마한 경우의 수이며, 이정도 규모라면 컴퓨터도 1초 안에 모든..
전구와 스위치( BOJ 2138 ) 문제 : https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 문제 파악하기 입력된 N개의 스위치를 적절하게 눌러서 우리가 원하는 상태로 바꿀 수 있는지, 만약 바꿀 수 있다면 눌러야 하는 스위치의 최소 횟수를 구하는 문제입니다. 만약 N의 값이 작다면 직접 모든 경우의 수를 확인할 수 있지만 N이 최대 100,000이기 때문에 좀 더 효율적인 알고리즘이 필요합니다. 다행히 스위치는 항상 바로 왼쪽과 오른쪽에 위치한 전구..
RPG( BOJ 1315 ) 문제 : https://www.acmicpc.net/problem/1315 1315번: RPG 준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다. 게임에는 총 N개의 www.acmicpc.net 문제 파악하기 경험치를 힘(STR)과 지력(INT)에 적절히 투자해서 클리어할 수 있는 퀘스트의 최댓값을 구하는 문제입니다. 각각의 퀘스트는 클리어를 할 수 있는 힘과 지력의 제한이 있으며, 캐릭터의 힘과 지력 중 어느 한 곳의 능력치가 특정 퀘스트의 힘과 지력 제한보다 크거나 같다면 해당 퀘스트를 클리어하고 경험치를 얻을 수 있습니다. 문제를 해결할 수 있는 가장 단순한 알..
복구( BOJ 15908 ) 문제 : https://www.acmicpc.net/problem/15908 15908번: 복구 예제 1에 대해, 3번째 수와 6번째 수를 지우면 {3, 1, 2}, {2, 1}, {3, 1, 3}이 된다. 예제 2에 대해, 1번째, 8번째, 9번째, 11번째, 16번째, 17번째, 19번째 수를 지우면 {4, 2, 5, 5}, {5, 1, 4, 5, 1}, {4, 2, 5, 2}가 된다 www.acmicpc.net 문제 파악하기 N개의 숫자(사용자 데이터)를 적절하게 지워서 조건에 맞는 사용자 데이터를 만드는 경우의 수 중, 지운 숫자들이 가진 가능성의 최댓값을 가장 작게 만드는 경우를 구하는 문제입니다. 단순히 숫자를 지우기에는 100,000개의 데이터가 너무 많기에 문제를 좀 더 단순화 시킬 필요가..
변신 이동 게임( BOJ 15906 ) 문제 : https://www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 문제 파악하기 게임 속 캐릭터를 (1, 1)에서 (r, c)까지 이동하는데 필요한 최소 턴 횟수를 구하는 문제입니다. 캐릭터는 1턴을 사용하여 상하좌우 인접한 1칸으로 움직이거나 t턴을 사용하여 변신 모드로 변신한 다음, 1턴을 사용하여 상하좌우 방향의 가장 가까운 워프 지점('#')으로 이동할 수 있습니다. 각각의 칸에서 이동할 수..
Mowing the Lawn( BOJ 5977 ) 문제 : https://www.acmicpc.net/problem/5977 5977번: Mowing the Lawn FJ has 5 cows whose efficiencies are 1, 2, 3, 4, and 5, in that order. He wants to choose some of the cows such that their total efficiency is maximized, but he cannot choose more than 2 consecutive cows. FJ chooses all cows but the third. The total effici www.acmicpc.net 문제 파악하기 N 마리의 소 중, 연속된 번호의 소를 K마리보다 많이 선택하지 않으면서 효율성이 최대가 되게..

티스토리툴바