18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 백트래킹 제목 NM과 K(1) 조건 시간 제한 : 2 초 메모리 제한 : 512 MB 문제 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다. 입력 첫째..
18198번: Basketball One-on-One The input consists of a single line with no more than 200 characters: the record of one game. The record consists of single letters (either A or B) alternating with single numbers (either 1 or 2), and includes no spaces or other extraneous characters. Each www.acmicpc.net 듀스 주의 제목 Basketball One-on-One 조건 시간 제한 : 초 메모리 제한 : MB 문제 Alice and Barbara played some friend..
14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net Trie / 이분탐색 / 해시 제목 접두사 찾기 조건 시간 제한 : 1 초 메모리 제한 : 1536 MB 문제 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 ..
+2 minimum 갱신 제목 선물 조건 시간 제한 : 1 초 메모리 제한 : 512MB 문제 N일 뒤는 동원이의 생일이다. 축하해 주자! 준원이는 동원이에게 생일 선물로 양말을 2X개 선물하려 한다. 양말은 시장에서 살 것이다. 연속한 이틀에 걸쳐서, 준원이는 매일 시장에서 양말을 X개씩 사서 트럭에 담아올 것이다. 시장에서 양말의 가격은 날마다 다를 수 있다. 오늘부터 i번째 날에, 양말은 하나에 A_i원이다. 동원이의 생일까지 N일 남았다! 남은 N일 가운데 연속한 이틀에 걸쳐 양말 2X개를 사는 데 드는 최소 비용은? 입력 첫째 줄에 N과 X가 공백을 사이에 두고 주어진다. 둘째 줄에 N일간 양말의 가격 1,2,⋯,A_1, A_2, ..., A_N이 공백을 사이에 두고 주어진다. 출력 연속한 이틀..
파스칼 삼각형 + DP 제목 Final Price 조건 시간 제한 : 1 초 메모리 제한 : 512MB 문제 파스칼 삼각형은 아래와 같은 모양으로 이루어져 있다. 양 끝을 제외한 각 수는 자신의 바로 왼쪽 위의 수와 바로 오른쪽 위의 수의 합으로 되어있다. 이때 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부를 생각하자. 정삼각형의 변과 그 내부에 있는 수들의 합을 구하고 싶다. 예를 들면, 3번 째 줄, 1번 째 수를 꼭짓점으로 하고 한 변이 포함하는 수의 개수가 4인 정삼각형과 그 내부에 있는 수의 합은 1+(1+3)+(1+4+6)+(1+5+10+10) = 42 이다. 주어진 R, C, W에 대해서 그에 해당하는 합을 구하는 프로그램을 작성하여라. ..
합 제목 Final Price 조건 시간 제한 : 2 초 메모리 제한 : 1024 MB 문제 Neverland has recently experienced a rapid rise in the inflation rate. The value of money is continuously decreasing, and citizens’ purchasing power is lowered daily. The government is trying to control the inflation rate by testing various methods, such as reducing the amount of money in the economy by increasing interest rates and promoting i..
벽을 부술 수 있는 경우와 부술 수 없는 경우를 나눠 경로 설정 제목 벽 부수고 이동하기 조건 시간 제한 : 2 초 메모리 제한 : 192 MB 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를..
배열의 두 값을 이용한 문제일 때 두 포인터를 꼭 체크해야한다 제목 조건 시간 제한 : 2 초 메모리 제한 : 256 MB 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. 예제 입력1 예제 출력1 10 1 2 3 4 5 6 7 8 9 10 8 N = int(input()) arr = sorted(lis..
돌이 1개 일 때는 상근이가 먼저 시작하므로 창영이가 이긴다 +1 +3 마다 결과를 뒤집어준다 제목 돌 게임 2 조건 시간 제한 : 1 초 메모리 제한 : 128 MB 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 예제 입력1 예제 출력1 4 SK N = int(input()) dp =..
1. 고객이 원하는 대형 스크린을 만들기 위해서는 4가지 조건 중 최적을 선택해야한다. (가로 해상도(pixel) / 세로 크기(mm)) (가로 크기(mm) / 세로 해상도(pixel)) (가로 크기(mm) / 세로 크기(mm)) (가로 해상도(pixel) / 세로 해상도(pixel)) 2. 모니터를 정방향으로, 90도 회전시켜 최소 모니터수를 구해 금액을 최소화한다. 제목 대형 스크린 조건 시간 제한 : 1 초 메모리 제한 : 128 MB 문제 상근이는 모니터를 여러개 붙여서 대형 모니터를 만드는 일을 하고 있다. 고객은 대형 모니터의 가로, 세로 해상도(픽셀)과 가로 세로 크기(밀리미터)를 상근이에게 주문한다. 상근이는 고객의 주문 값보다 크거나 같은 해상도, 크거나 같은 크기의 대형 모니터를 만들어..
22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net BFS DFS 제목 항체 인식 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 UNO는 빅데이터와 딥러닝 기술을 통해 학습한 인공지능을 이용해 의학 전문가들의 판단에 도움을 주는 Medical AI 솔루션을 개발하는 전문 기업이다. VUNO는 최근 SP라는 강력한 새로운 촬영 기법을 개발했다. 이 기법을 사용하면 인체 조직이 격자 형태로 표현되고, 격자의 각 칸에는 해당 부분의 각종 분석 결과를 압축한 하나..
25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다 제목 인사성 밝은 곰곰이 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 알고리즘 입문방 오픈 채팅방에서는 새로운 분들이 입장을 할 때마다 곰곰티콘을 사용해 인사를 한다. 이를 본 문자열 킬러 임스는 채팅방의 기록을 수집해 그 중 곰곰티콘이 사용된 횟수를 구해 보기로 했다. ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채..
