본문 바로가기
X/인알그 스터디

5일차

by 유시은 2020. 9. 15.

2020-09-06
초급 : 15786 Send me the money (Bronze II)

www.acmicpc.net/problem/15786

 

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)

www.acmicpc.net/problem/14620

 

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)

www.acmicpc.net/problem/17268

 

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;
}

 

이 수열을 카탈란 수 라고 한단다.

'X > 인알그 스터디' 카테고리의 다른 글

6일차  (0) 2020.09.15
5일차  (0) 2020.09.15
4일차  (0) 2020.09.15
3일차  (0) 2020.09.15
2일차  (0) 2020.09.05
1일차  (0) 2020.09.05

댓글0