한시간 동안 풀었는데 결국 풀지 못했다.
[2 3 1]
의 뜻이 뭔지 이해가 안 되었던게 컸던 것 같다.
처음에 생각했던 것은 tetris 니까 n개의 블록을 잘 내려서 줄을 없애라는 줄 알았다.
이렇게 하면 1개가 있는 자리에 n개의 블록을 1개씩 보내주면 모두 2개 이상이 되어 두 줄을 없앨 수 있어서
2가 답인 줄 알았다.
해석할 때 시간이 오래 걸릴 것 같아 파파고번역기로 번역을 해서 한게 좋지 않은 영향을 준 것 같다.
실제 문제는 Hack 단계에서 다른 사람의 코드를 보니 3개의 열이 있고 주어진 블록을 해당열에다가 쌓는 형식이었다.
문제만 제대로 이해했으면 금방 풀었을 텐데 아쉽다.
Accept 받은 코드
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <limits.h>
#include <queue>
#include <stack>
using namespace std;
int tb1[100001];
int che[100001];
bool doo[100001];
int n, m;
int main(void)
{
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int k;
cin >> k;
tb1[k]++;
}
int ans = INT32_MAX;
for (int i = 1; i <= n; ++i) {
ans = min(ans, tb1[i]);
}
cout << ans << endl;
return 0;
}
B. Lecture Sleep
주인공은 잠이 많아 수업시간에 조는데 깨어있는 동안은 열심히 적는다.
단 한번 깨울 수 있는데 깨우면 m분만큼 필기를 한다.
최대한 많이 필기 하는 양을 출력
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <limits.h>
#include <queue>
#include <stack>
using namespace std;
int tb1[100001];
bool che[100001];
bool doo[100001];
stack<int> st;
int n, m;
int main(void)
{
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> tb1[i];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
che[i] = k;
if (k == 1) {
st.push(i);
ans += tb1[i];
}
}
int tempansmax = 0;
for (int i = 0; i < n-m+1; ++i) {
int tempans = ans;
for (int k = i; k < i + m; ++k) {
if (che[k] == 0) {
tempans += tb1[k];
}
}
tempansmax = max(tempansmax, tempans);
}
cout << tempansmax << endl;
return 0;
}
Time Out 날 걸 확신하고 쓴 코드.
for (int k = i; k < i + m; ++k) {
if (che[k] == 0) {
tempans += tb1[k];
}
}
이 코드를 조금 만 더 최적화 하면 될 것 같다.
바뀌는 부분은 맨 처음과 맨 끝이므로
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <limits.h>
#include <queue>
#include <stack>
using namespace std;
int tb1[100001];
bool che[100001];
bool doo[100001];
stack<int> st;
int n, m;
int main(void)
{
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> tb1[i];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
che[i] = k;
if (k == 1) {
st.push(i);
ans += tb1[i];
}
}
int tempans = ans;
int tempansmax = 0;
for (int k = 0; k < m; ++k) {
if (che[k] == 0) {
tempans += tb1[k];
}
}
for (int i = 1; i < n-m+1; ++i) {
if (che[i - 1] == 0) {
tempans -= tb1[i - 1];
}
if (che[i + m - 1] == 0) {
tempans += tb1[i + m - 1];
}
tempansmax = max(tempansmax, tempans);
}
cout << tempansmax << endl;
return 0;
}
이렇게 수정을 했는데 TC4에서 Wrong answer 이 나왔다.
int tempans = ans;
int tempansmax = 0;
for (int k = 0; k < m; ++k) {
if (che[k] == 0) {
tempans += tb1[k];
}
}
for (int i = 1; i < n-m+1; ++i) {
if (che[i - 1] == 0) {
tempans -= tb1[i - 1];
}
if (che[i + m - 1] == 0) {
tempans += tb1[i + m - 1];
}
tempansmax = max(tempansmax, tempans);
}
여기서 tempansmax가 for(int i=1 로 들어가기 전에 k=0~m 까지 더한 값을 저장하고 가야 하는데 놔두고 가서 TC4가
k=0에서 시작해서 하는게 최대값인 경우라 Wrong Answer 이었다 보다
Accept 받은 코드
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <limits.h>
#include <queue>
#include <stack>
using namespace std;
int tb1[100001];
int che[100001];
bool doo[100001];
int n, m;
int main(void)
{
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> tb1[i];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
che[i] = k;
if (k == 1) {
ans += tb1[i];
}
}
int tempans = ans;
for (int k = 0; k < m; ++k) {
if (che[k] == 0) {
tempans += tb1[k];
}
}
int tempansmax = tempans;
for (int i = 1; i < n-m+1; ++i) {
if (che[i - 1] == 0) {
tempans -= tb1[i - 1];
}
if (che[i + m-1] == 0) {
tempans += tb1[i + m-1];
}
tempansmax = max(tempansmax, tempans);
}
cout << tempansmax << endl;
return 0;
}