2020-09-06
초급 : 15786 Send me the money (Bronze II)
15786번: Send me the money
입력의 첫째 줄에 석규가 기억하는 원본 알파벳의 수 N(1 ≤ N ≤ 100)과 포스트잇의 개수 M(1 ≤ M ≤ 1000)이 주어진다. 다음 줄에 길이가 N인 알파벳 대문자로 이루어진 문자열 S가 주어진다. 이 후 M
www.acmicpc.net
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
S = input()
for _ in range(M):
s = S
q = input()
while len(s)>0:
p = q.find(s[0])
if p==-1:
break
s = s[1:]
q = q[p+1:]
print(["false","true"][len(s)==0])
S가 포스트잇에 적힌 문자열의 부분 문자열인지 묻는 문제이다.
S에 적힌 순서대로 왼쪽부터 탐색하면 된다.
중급 : 14620 꽃길 (Silver II)
14620번: 꽃길
2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int N, res = 2147483647;
int board[10][10];
bool visit[10][10];
int getCost(int r, int c) {
return board[r][c] + board[r - 1][c] + board[r][c - 1] + board[r + 1][c] + board[r][c + 1];
}
void setVisit(int r, int c, bool tf) {
visit[r][c] = visit[r - 1][c] = visit[r][c - 1] = visit[r + 1][c] = visit[r][c + 1] = tf;
}
bool getVisit(int r, int c) {
return visit[r][c] || visit[r - 1][c] || visit[r][c - 1] || visit[r + 1][c] || visit[r][c + 1];
}
void dfs(int flower, int cost, int row, int col) {
if (flower == 3) {
res = min(res, cost);
return;
}
for (int r = 1; r < N - 1; ++r) {
for (int c = 1; c < N - 1; ++c) {
if (r < row || (r == row && c < col)) continue;
if (getVisit(r, c)) continue;
setVisit(r, c, true);
dfs(flower + 1, cost + getCost(r, c), r, c);
setVisit(r, c, false);
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
cin >> board[r][c];
}
}
for (int r = 1; r < N - 1; ++r) {
for (int c = 1; c < N - 1; ++c) {
setVisit(r, c, true);
dfs(1, getCost(r, c), r, c);
setVisit(r, c, false);
}
}
cout << res;
return 0;
}
열심히 백트래킹하면 된다.
꽃잎의 모양이 특이하므로 비용, visit에 관한 함수를 만들어두면 좋다.
고급 : 17268 미팅의 저주 (Gold III)
17268번: 미팅의 저주
인하대 컴퓨터 공학과에 재학 중인 이산이는 오랜만에 미팅을 나가 볼까 한다. 미팅은 N명이 원탁에 앉아서 진행된다고 한다. 질투가 난 이산이 친구 명기는 X의 저주를 걸었다. 그 저주는 N명이
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll dp[5001];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n; n /= 2;
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
dp[i] += dp[j] * dp[i - 1 - j];
dp[i] %= 987654321;
}
}
cout << dp[n];
return 0;
}
이 수열을 카탈란 수 라고 한단다.
댓글